Cirno invented a new game involving binary splitting. Specifically, in each step of the game, the following is performed: Given a sequence of $k$ numbers $X_1, X_2, \ldots, X_k$, she will split the sequence into two contiguous subsequences: $X_1, X_2, \ldots, X_m$ and $X_{m+1}, \ldots, X_k$ with $1 \le m \le k - 1$. Then, she will choose one of the two subsequences to keep, and the other will be discarded. The reward for this step is the sum of all elements in the chosen subsequence. This chosen subsequence will continue to be split in the next steps. Reisen receives an invitation to play this game. She is given an initial sequence of $n$ elements $a_1, a_2, \ldots, a_n$, and must play until only one element remains (i.e., no more splits are possible). Reisen always makes the splits, while Cirno gets to choose which of the two resulting subsequences to keep. Reisen wants to maximize her total score, while Cirno plays optimally to minimize Reisen’s score. Help Reisen compute the maximum score she can achieve, assuming both players play optimally.
### Input
- The first line contains a positive integer $n.$
- The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n.$
### Output
- Print the minimum cost of the game.
### Constraints
- $1 \leq n \leq 2000.$
- $1 \leq a_1, a_2, \ldots, a_n \leq 2000.$
### Example
Input
```
6
9 5 3 2 3 7
```
Output
```
19
```
