JOI and IOI are twins. JOI has recently been into baking, and today, when he baked a cake and was about to eat it, IOI smelled it and came over, so the two of them decided to share the cake.

The cake is circular. Cuts are made radially from a point to divide the cake into $N$ pieces, which are numbered from $1$ to $N$ in counterclockwise order. That is, for $1 \le i \le N$, the $i$-th piece is adjacent to the $(i-1)$-th piece and the $(i+1)$-th piece (where the $0$-th piece is considered the $N$-th piece, and the $(N+1)$-th piece is considered the $1$-st piece). The size of the $i$-th piece is $A_i$, and because the cutting was done very poorly, all $A_i$ are distinct values.

Figure 1: Example of a cake ($N = 5, A_1 = 2, A_2 = 8, A_3 = 1, A_4 = 10, A_5 = 9$)

They decided to divide these $N$ pieces between JOI and IOI. The division process is as follows:

1. First, JOI chooses and takes any one of the $N$ pieces.
2. After that, starting with IOI, IOI and JOI take turns picking one piece at a time from the remaining pieces. However, a piece can only be picked if at least one of its two adjacent pieces has already been taken. If there are multiple pieces that can be picked, IOI chooses the largest one among them, and JOI can choose any one he likes among them.

JOI wants to maximize the total size of the pieces he eventually takes.

Input

Read the following from standard input:

• The first line contains an integer $N$, representing that the cake is divided into $N$ pieces.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains an integer $A_i$, representing the size of the $i$-th piece.

Output

Output the maximum total size of the pieces JOI can take in one line.

Constraints

All input data satisfies the following conditions:

• $1 \le N \le 2\,000$.
• $1 \le A_i \le 1\,000\,000\,000$.
• All $A_i$ are distinct.

Subtasks

Subtask 1 [15 points]

• $N \le 20$ is satisfied.

Subtask 2 [45 points]

• $N \le 300$ is satisfied.

Subtask 3 [40 points]

• No additional constraints.

Examples

Input 1

5
2
8
1
10
9

Output 1

18

Note 1

It is optimal for JOI to take the pieces as follows:

1. JOI takes the 2nd piece. The size of this piece is 8.
2. IOI takes the 1st piece. The size of this piece is 2.
3. JOI takes the 5th piece. The size of this piece is 9.
4. IOI takes the 4th piece. The size of this piece is 10.
5. JOI takes the 3rd piece. The size of this piece is 1.

Ultimately, the total size of the pieces JOI took is $8 + 9 + 1 = 18$.

Input 2

8
1
10
4
5
6
2
9
3

Output 2

26

Input 3

15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789

Output 3

3600242976