Problem G
Fold it Felix!

Felix the carpenter and his friend Travis own a furniture company and are making a stock of new drawers. Travis was fascinated by the new Efesto drawer and he is trying to convince his partner Felix to buy a stock of them.

These drawers comes with a very long instruction sheet that is very peculiar, since it can be folded in many different ways, to fit differength lengths. It is a very long piece of paper with filding lines that separate each page of the instruction sheet. Pages are numbered from $1$ to $N$ and each page have different length to fit all the instructions needed for one step of the assembly of the drawer (although there might be two pages of the same length). The folding lines can only be folded in a clockwise direction by 180 degrees. If a folded page spans a folding line then that line cannot be folded and you can fold page $i$ only if no page $i < j \leq N$ has been folded. Finally, the end of the last page can be in the middle of the folded insctruction sheet.

Help Felix and Travis finding which is the smallest length the instruction sheet can be folded into.

Input

The file contains two lines. The first line contains one integer $N$ with the number of pages of the instruction sheet. The second line contains $N$ integers $\ell _1,\ldots ,\ell _ N$ each one reporting the length of each page in the same order they can be folded.

Output

You need to write a single line with an integer: the smallest length for the folded instruction sheet.

Constraints

• The number of pages $N$ is between $1$ and $200\, 000$.

• The length of each page is between $1$ and $100\, 000$.

Example

In the first sample case depicted in the figure below at first we have the unfolded instruction sheet with the four pages numbered $1$, $2$, $3$, and $4$ of lengths $4$, $3$, $2$, and $2$ respectively, with the folding lines $A$, $B$, and $C$.

• In the first step we fold the folding line $A$ causing page $1$ to overlap entirely page $2$ and partially page $3$.

  Note: Since page $1$ overlaps partially page $3$, folding line $B$ is blocked and cannot be folded.

• In the second step we fold the folding line $C$ obtaining the smallest folding length for the instruction sheet which is given by pages $2$ and $3$ whose sum is $5$.

  Note: The end of page $4$ is not at the end of the folded instruction sheet.

Note: The order of folding the pages must be from page $1$ to page $4$ and equivalently from folding line $A$ to folding line $C$. I.e., we cannot fold folding line $C$, then folding line $B$, then folding line $A$ with a resulting length of $4$.

Detailed example.

4
4 3 2 2

5

10
5 6 3 4 8 6 2 1 8 5

9