Problem Description

JOI-kun and IOI-chan are twin siblings. JOI-kun has recently become obsessed with making desserts. Today he baked a cake to eat by himself, but as soon as it came out of the oven, IOI-chan smelled it and came over, so the two decided to share the cake.

The cake is circular. Starting from some point, radial cuts are made to divide the cake into $N$ pieces, and these pieces are numbered $1$ to $N$ in counterclockwise order. That is, for $1 \le i \le N$, piece $i$ is adjacent to pieces $i-1$ and $i+1$ (where piece $0$ is considered to be piece $N$, and piece $N+1$ is considered to be piece $1$). The size of piece $i$ is $A_i$, but because the cutting skill is poor, all values $A_i$ are different from each other.

:::align{center}

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

They decide to distribute the $N$ pieces of cake according to the following rules:

1. First, JOI-kun chooses any one piece from the $N$ pieces and takes it.
2. Then, starting with IOI-chan, IOI-chan and JOI-kun take turns taking one piece at a time from the remaining pieces. However, they can only take a piece such that at least one of its adjacent pieces has already been taken. When there are multiple pieces that can be taken, IOI-chan must choose the largest one among them, while JOI-kun may choose any one among them.

JOI-kun wants to maximize the sum of the sizes of all pieces he finally takes.

Task

Given the number of pieces $N$ and the sizes of the $N$ pieces, write a program to compute the maximum possible sum of the sizes of the pieces that JOI-kun can obtain.

Input Format

Read the following input from standard input.

• The first line contains an integer $N$, meaning the cake is cut into $N$ pieces.
• In the next $N$ lines, line $i$ ($1 \le i \le N$) contains an integer $A_i$, meaning the size of piece $i$ is $A_i$.

Output Format

Output one line to standard output containing an integer, meaning the maximum possible sum of the sizes of the pieces that JOI-kun can obtain.

5
2
8
1
10
9

18

8
1
10
4
5
6
2
9
3

26

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

3600242976

Hint

Sample Explanation 1

It is optimal for JOI-kun to take the cake in the following way:

1. JOI-kun takes piece $2$. Its size is $8$.
2. IOI-chan takes piece $1$. Its size is $2$.
3. JOI-kun takes piece $5$. Its size is $9$.
4. IOI-chan takes piece $4$. Its size is $10$.
5. JOI-kun takes piece $3$. Its size is $1$.

In the end, the sum of the sizes of the pieces JOI-kun takes is $8 + 9 + 1 = 18$.

Constraints

All input data satisfy the following conditions:

• $1 \le N \le 2000$.
• $1 \le A_i \le 1000000000$.
• All $A_i$ are distinct.

Subtasks

Subtask 1 [15 points]

• Satisfies $N \le 20$.

Subtask 2 [45 points]

• Satisfies $N \le 300$.

Subtask 3 [40 points]

There are no additional constraints.

Translated by DeepSeek V3.2.

Translated by ChatGPT 5