Two lumberjacks (Bajtek and Bitek) working at the same speed will chop $n$ pieces of wood, initially arranged in a stack. Chopping the $i$-th piece of wood takes $a_i$ minutes. Whenever one of the lumberjacks finishes chopping their current piece, they take the next one from the stack. If both finish at the same time, Bajtek takes the next piece first.

Calculate the latest possible moment when all wood chopping is finished, if the pieces of wood are arranged in the stack in an exceptionally unfortunate order.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 10^6$) representing the number of pieces of wood. The second line contains a sequence of $n$ positive integers $a_1, a_2, \dots, a_n$ representing the chopping times of the individual pieces of wood.

Let $A = a_1 + a_2 + \dots + a_n$ denote the sum of the chopping times. The inequality $A \le 5\,000\,000$ holds.

Output

In the only line of output, print a single integer representing the longest possible working time for the lumberjacks.

Examples

Input 1

3
2 3 1

Output 1

4

Note

The result 4 is achievable if, for example, the pieces of wood are in the order 1, 2, 3. Then Bajtek will start chopping piece 1, and Bitek will start with piece 2. After 1 minute, Bajtek will take piece 3, and finally, after 4 minutes, all pieces will be chopped.

Evaluation tests

• Test 1: $n = 6$, $a_i = i$; the answer is 13.
• Test 2: $n = 1000$, $a_i = 1$; the answer is 500.
• Test 3: $n = 10$, $a_i = 2^{i-1}$; the answer is 767.
• Test 4: $n = 2$, $a_i = 2\,500\,000$; the answer is 2\,500\,000.

Subtasks