커닝시티 헤어샵

‘커닝시티 헤어샵’에는 원장 돈 지오바네와 보조 안드레아가 일하고 있다. 어느 날, 이 둘에게 헤어 스타일링을 받으려는 고객 $N$ 명이 한 줄로 기다리고 있다.

돈 지오바네와 안드레아는 각 고객이 서비스받는 시간을 알고 있다. 고객들은 줄을 선 순서대로 서비스를 받아야 한다. 돈 지오바네와 안드레아는 협력해서 일하여 최대 $2$ 명의 고객을 동시에 서비스할 수 있다. 만약 두 사람이 동시에 $2$ 명의 고객을 서비스하는 경우, 두 고객 중 서비스받는 시간이 오래 걸리는 쪽의 시간이 걸린다.

돈 지오바네와 안드레아가 모든 고객을 서비스하는 데 걸리는 최소 시간을 계산하는 프로그램을 작성하라.

입력 형식

첫 줄에 고객의 수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 500\,000$)

그다음 줄에 $N$ 명의 고객이 서비스받는 시간을 나타내는 정수 $N$ 개가 줄을 선 순서대로 공백으로 구분되어 주어진다.

각 고객이 서비스받는 시간은 $1$ 이상 $1\,000\,000\,000$ 이하다.

출력 형식

첫 줄에 모든 고객을 서비스하기 위해 필요한 최소 시간을 출력한다.

예제 1

4
2 3 4 3

7

예제 2

4
1 3 3 1

5

예제 설명

입력 예제 1에서 첫 번째와 두 번째 고객을 동시에 서비스해서 시간 $3$이 걸리고, 세 번째와 네 번째 고객을 동시에 서비스해서 시간 $4$가 걸린다. 따라서, 전체 시간은 $7$이며 이 방법이 최선이다.

입력 예제 2에서 첫 번째 고객을 서비스하여 시간 $1$이 걸리고, 두 번째와 세 번째 고객을 동시에 서비스하여 시간 $3$이, 네 번째 고객을 서비스하여 시간 $1$이 걸린다. 따라서, 전체 시간은 $5$이며 이 방법이 최선이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설