You have a huge block of chocolate of size 1xN. However, just as you are about to eat it, Kang the penguin comes along and demands that you share it with him! Thus, you begrudgingly decide to break the chocolate into two sets of pieces such that the total size of each set is N/2. However, it so happens that this block of chocolate is unnaturally hard at some points and unnaturally easy to break at some points. Thus, you want to ensure that you expend the minimum amount of effort to share your chocolate with the greedy penguin.
The chocolate can only be broken at whole number portions along its length, so as to preserve its taste. Given a1, a2, ... , aN-1, where ai represents the amount of effort needed to break the block of chocolate between piece i and piece i+1, output the minimum total effort required to create two sets of pieces of chocolate such that the total size of each one is N/2.
Input
The first line of the input consists of one even integer N (2 ≤ N ≤ 10,000).
The next N-1 lines of input contain one integer each, representing the values of ai in order (1 ≤ ai ≤ 10,000).
Output
Output one integer, the minimum total effort required
Sample Input 1
6
1
8
12
6
2
Sample Output 1
7
Explanation for Sample Output 1
Dividing the piece of chocolate between pieces 1 and 2, as well as between pieces 4 and 5 require 1+6=7 units of effort. Then, we keep pieces [1,1] and [5,6] for ourselves, while giving away [2,4] to the penguin. This is optimal.