Cutting the Cake 2

JOI and IOI are twin siblings. JOI has been absorbed in baking lately, so he baked a cake today too. The moment it came out of the oven, IOI smelled it and came over, so the two decided to share the cake.

The cake is round. Straight cuts from one point outward split the cake into $N$ pieces, and the pieces are numbered $1$ to $N$ counterclockwise. That is, for every $i$ with $1 \le i \le N$, piece $i$ touches piece $i-1$ and piece $i+1$, where piece $0$ means piece $N$ and piece $N+1$ means piece $1$. Piece $i$ has size $A_i$, and because the cutting was clumsy, all $A_i$ are different.

The two split the pieces as follows.

1. First, JOI takes any one of the $N$ pieces.
2. After that, starting with IOI, IOI and JOI alternately take one of the remaining pieces each. A piece may be taken only if at least one of its two neighbors has already been taken by someone. When several pieces can be taken, IOI takes the largest of them, and JOI can take whichever piece he wants.

JOI wants the total size of the pieces he takes to be as large as possible.

Given the number of pieces $N$ and the size of each piece, write a program that finds the largest total size JOI can take.

The first line contains the number of pieces $N$.

Each of the next $N$ lines contains one integer. Line $i$ contains $A_i$, the size of piece $i$.

Print the largest total size JOI can take on one line.

• $1 \le N \le 2000$
• $1 \le A_i \le 10^9$
• All $A_i$ are different.