Problem Description

There are $N$ cards stacked, each with a single integer written on it. The $i$-th card from the top has the integer $a_i$ written on it.

Alice and Bob decided to play a game using these cards.

Starting with Alice, they take turns to pick one or more cards from the top of the remaining cards, and write down the sum of the integers they picked.

When all cards are gone, the score of the game is calculated using the written integers.

If the number of written integers is $K$, the score of the game is the smallest integer that is at least the $(K+1)/2$-th smallest value among them.

Both players know the integers written on the cards beforehand. Alice wants to maximize the score, while Bob wants to minimize it.

What will be the score of the game when both players play optimally?

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ ... $ a_{N-1} $ $ a_N $

Output Format

Output the score of the game when both players play optimally.

Sample Input and Output

Sample Input #1

2
1 -1

Sample Output #1

1

Sample Input #2

3
3 1 4

Sample Output #2

8

Notes/Hints

Constraints

• $1 \leq N \leq 1000$
• $0 \leq |a_i| \leq 10^9$
• All inputs are integers.

Sample Explanation 1

If Alice picks $\{1, -1\}$ first, the written integers are $\{0\}$, and the score is $ 0 $. If Alice picks $\{1\}$ first, Bob will pick $\{-1\}$, resulting in written integers $\{1, -1\}$, and the score is $ 1 $. Therefore, Alice prefers to pick $\{1\}$, and the score is $ 1 $.

见题面 Input 部分

见题面 Output 部分