Problem Description

JOI and IOI are twin siblings. JOI has recently become obsessed with baking, and today he plans to bake and eat a cake. However, just as it was done baking, IOI, drawn by the smell, came and they decided to share the cake.

The cake is circular. It is cut radially from a certain point into $ N $ pieces, numbered from $ 1 $ to $ N $ in a counterclockwise direction. Thus, for $1 \leq i \leq N$, the $ i $th piece is adjacent to the $ i - 1 $th and $ i + 1 $th pieces (with the $ 0 $th piece considered as the $ N $th piece and the $ N + 1 $th piece considered as the $ 1 $st piece). The size of the $ i $th piece is $ A_i $, and due to JOI's poor cutting skills, all $ A_i $ are different.

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 the $ N $ pieces as follows:

1. First, JOI chooses any one of the $ N $ pieces to take.
2. Then, starting with IOI, they alternate taking one piece each until all pieces are taken. However, each piece can only be taken if at least one of its adjacent pieces has already been taken. When multiple pieces are available, IOI always chooses the largest one, while JOI can choose any of them.

JOI wants to maximize the total size of the pieces he ends up with.

Input Format

Read the following input from standard input:

• The first line contains an integer $ N $, indicating that the cake is divided into $ N $ pieces.
• The next $ N $ lines contain integers $ A_i $, indicating the size of the $ i $th piece.

Output Format

Output to standard output a single integer representing the maximum total size of the pieces JOI can take.

Sample Input and Output

Sample Input #1

5
2
8
1
10
9

Sample Output #1

18

Sample Input #2

8
1
10
4
5
6
2
9
3

Sample Output #2

26

Sample Input #3

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

Sample Output #3

3600242976

Notes/Hints

Task

Given the number of cake pieces $ N $ and the sizes of these pieces, write a program to determine the maximum total size of the pieces JOI can take.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [15 points]

• $N \leq 20$.

Subtask 2 [45 points]

• $N \leq 300$.

Subtask 3 [40 points]

No additional constraints.

Sample Explanation 1

JOI can take the pieces optimally as follows:
1. JOI takes the 2nd piece (size 8).
2. IOI takes the 1st piece (size 2).
3. JOI takes the 5th piece (size 9).
4. IOI takes the 4th piece (size 10).
5. JOI takes the 3rd piece (size 1).

The total size of the pieces JOI takes is $ 8 + 9 + 1 = 18 $.

Sample Explanation 2

见题面 Input 部分

见题面 Output 部分