P15817 [JOI 2015 Final] Cake Sharing 2 / Cake 2

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.

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 one line to standard output containing an integer, meaning the maximum possible sum of the sizes of the pieces that JOI-kun can obtain.

### 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