길이가 양수인 $n$개의 부분으로 이루어진 접는 막대가 있습니다. 각 부분은 경첩 (늘어나는 끈)으로 연결되어 있어 각 경첩에서 180도 접을 수 있습니다. 하나 이상의 경첩에서 접은 뒤 막대의 길이를 포장 길이라고 합니다. 접는 방법에 따라 포장 길이가 달라질 수 있습니다.

다음 방식으로 막대를 접는다는 조건 아래 최소 포장 길이를 구해야 합니다. 먼저 막대의 각 부분을 수평선 위에 놓습니다. 그런 다음 왼쪽에서 오른쪽으로 시계 방향으로 막대를 접습니다. 접는 동안 각 경첩의 왼쪽에 붙어 있는 부분은 시계 방향으로 180도 회전하거나 전혀 회전하지 않습니다.

예를 들어 아래 그림은 각 부분의 길이의 합이 $10$인 네 부분짜리 막대를 보여 줍니다. 그림에서 왼쪽부터 길이는 $3,2,2,3$이며, 경첩은 ①, ②, ③으로 표시되어 있습니다.

이 예에서는 경첩 ①과 ② 모두에서 접을 수 없습니다. 경첩 ①에서 접은 다음 경첩 ②에서 접으면 경첩 ②를 지나가는 길이 $3$인 부분이 부러지기 때문입니다. 경첩 ②에서만 접으면 포장 길이는 $5$입니다. 경첩 ①과 ③에서 차례로 접으면 아래 그림과 같이 포장 길이는 $4$입니다.

접는 막대의 각 부분 길이의 수열이 주어질 때, 막대의 최소 포장 길이를 출력하는 프로그램을 작성하세요.

입력

프로그램은 표준 입력에서 읽어야 합니다. 입력은 접는 막대의 부분 수인 정수 $n$ ($2\le n\le100000$)이 있는 줄로 시작합니다. 다음 줄에는 막대의 가장 왼쪽 부분부터 가장 오른쪽 부분까지의 길이를 순서대로 나타내는 양의 정수 $n$개가 있습니다. 각 부분의 길이는 $20000$ 이하입니다.

출력

프로그램은 표준 출력에 써야 합니다. 정확히 한 줄을 출력하세요. 그 줄에는 최소 포장 길이를 나타내는 양의 정수가 있어야 합니다.

다음은 세 테스트 케이스의 예제 입력과 출력입니다.

예제

입력 1

4
3 2 2 3

출력 1

4

입력 2

5
1 1 1 1 1

출력 2

1

입력 3

7
1 3 2 3 4 2 2

출력 3

6