28076번 - 멀티탭 충분하다

역사와 전통의 인하대학교 PS소모임 CTP는 스터디를 위해 멀티탭 세팅을 수없이 하여, 이제 멀티탭을 가지고 놀 정도의 수준이 되었다. 말 그대로 가지고 놀고 있는데, 2구부터 10⁸구까지 다양한 멀티탭을 보유하고 있다. $k$구 멀티탭은 콘센트가 $k$개 있는 멀티탭을 뜻하며, 다음은 3구 멀티탭의 예시이다.

위에서 본 3구 멀티탭	3구 멀티탭의 바닥 면

모든 멀티탭은 일자로 곧게 뻗은 모양으로, 콘센트가 동일한 간격으로 배치되어 있다. 특히 양 끝 콘센트의 바닥면에는 플러그가 있어 멀티탭 위에 다른 멀티탭을 꽂을 수 있다. 콘센트는 멀티탭의 긴 방향과 평행한 직선에 대해 30도 기울어져 있고, 위에 꽂는 멀티탭의 긴 방향과 평행한 직선은 그에 대해 수직이다.

CTP는 $N$개의 멀티탭을 가지고 있고, 각 멀티탭의 콘센트의 수는 $a_1, a_2, ..., a_N$이다. 멀티탭을 $N$층으로 쌓고 위에서 봤을 때 보이는 콘센트의 수의 최솟값을 구하여라. 단, 멀티탭의 콘센트를 제외한 부분과 원근은 무시한다.

첫째 줄에 멀티탭의 수 $N$이 주어진다.

둘째 줄에 각 멀티탭의 콘센트의 수를 나타내는 $a_1,a_2,...,a_N$이 공백으로 구분되어 주어진다.

문제의 정답에 해당하는 정수를 출력한다.

• 1 ≤ $N$ ≤ 200,000
• 2 ≤ 각 멀티탭의 콘센트의 수 ≤ 10⁸