Cutting the Cake 2

Time limit2sMemory limit512 MB

Summary

JOI chooses the first slice of a round cake, then both sides take exposed ends in turn against an opponent who always takes the larger end.

Level: Medium7 of 10
Topics: Game theory, Dynamic programming, Intervals
Solved: No attempts yet

Problem

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.

First, JOI takes any one of the $N$ pieces.
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.

Input

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$ .

Output

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

Constraints

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

Examples4

Example 1
Input
```
5
2
8
1
10
9
```
Expected output
```
18
```
Example 2
Input
```
8
1
10
4
5
6
2
9
3
```
Expected output
```
26
```

Example 3

Input

Expected output

3600242976

Example 4
Input
```
1
1000000000
```
Expected output
```
1000000000
```