Cirno invented a new game involving binary search. Specifically, each step of the game proceeds as follows: Given a sequence of $k$ numbers $X_1, X_2, \ldots, X_k$, she will split the sequence into two consecutive subarrays $X_1, X_2, \ldots, X_m$ and $X_{m+1}, \ldots, X_k$ with $1 \leq m \leq k-1$. She then chooses one of the subarrays to continue the binary search, and the cost of choosing a subarray is the sum of all its elements. The subarray not chosen is discarded. Receiving an invitation to play the game from Cirno, Reisen is given a sequence of $n$ elements $a_1, a_2, \ldots, a_n$ and plays until it is no longer possible to split the sequence (only one element remains). Reisen wants to play optimally to minimize the total cost of the game. Help Reisen calculate the minimum cost to complete the game.
### 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
```
