#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

You have a huge block of chocolate of size 1x*N*. 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 *a _{1}*,

*a*, ... ,

_{2}*a*, where

_{N-1}*a*represents the amount of effort needed to break the block of chocolate between piece

_{i}*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 *a _{i}* in order (1 ≤

*a*≤ 10,000).

_{i}## 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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 20 | 1s | 32MB | Average |

2 | 0 | 1 | 1s | 32MB | Average |

### Judge Compile Command

g++-8 ans.cpp -o chocolate -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512