Cirno invented a new game involving binary search. Specifically, each step of the game proceeds as follows: Given a sequence of k numbers X1,X2,…,Xk, she will split the sequence into two consecutive subarrays X1,X2,…,Xm and Xm+1,…,Xk with 1≤m≤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 a1,a2,…,an 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 a1,a2,…,an.
### Output
- Print the minimum cost of the game.
### Constraints
- 1≤n≤2000.
- 1≤a1,a2,…,an≤2000.
### Example
Input
6953237
Output
19
