AT_joi2015ho_b ケーキの切り分け２ (Cake 2)
题目描述
# 「JOI 2014/2015 决赛」分蛋糕 2
**译自 [JOI 2014/2015 决赛](https://www.ioi-jp.org/joi/2014/2015-ho/index.html) T2「[ケーキの切り分け２](https://www.ioi-jp.org/joi/2014/2015-ho/2015-ho.pdf)」**
JOI 君和 IOI 酱是双胞胎兄妹。 JOI 君最近闲暇时常常会做甜点。今天 JOI 君也烤了蛋糕吃，IOI 酱立马嗅到了蛋糕的香气于是跑来想分着吃。
蛋糕是圆形的，从蛋糕中某点开始将蛋糕放射状切为 $ N $ 块，按逆时针顺序编号为 $ 1 $ 到 $ N $ 。也就是说，对任意 $ i $ 来说 $ (1 \leq i \leq N) $ ，第 $ i $ 块蛋糕紧挨着第 $ i-1 $ 块与第 $ i+1 $ 块（不过第 $ 0 $ 块相当于第 $ N $ 块，第 $ N+1 $ 块相当于第 $ 1 $ 块）。第 $ i $ 块蛋糕的大小为 $ A_i $ 。由于切蛋糕的人刀功很不好，所以 $ A_i $ 互不相同。
JOI 君和 IOI 酱按照以下的方法分这 $N$ 块蛋糕：
1. 首先 JOI 君从这 $ N $ 块蛋糕中任选一块取走；
2. 然后，从 IOI 酱开始， IOI 酱和 JOI 君交替地从剩下的蛋糕中选出一块取走。不过，当且仅当一块蛋糕两旁的蛋糕至少有一块已经被选择，这块蛋糕才能被选择。如果可供选择的蛋糕有多个， IOI 酱会选择最大的一个，而 JOI 君可以任选一个。
JOI 君想让自己所得到的蛋糕大小的合计值最大。
#### 任务
给出蛋糕的块数 $ N $ 和这 $ N $ 块蛋糕的大小。请编写程序求出 JOI 君得到的蛋糕大小的总和的最大值。
输入格式
无
输出格式
无
说明/提示
JOI 君依次进行以下操作时为最优解：
1. JOI 君选择第 $ 2 $ 块蛋糕，这块蛋糕的大小为 $ 8 $；
2. IOI 酱选择第 $ 1 $ 块蛋糕，这块蛋糕的大小为 $ 2 $；
3. JOI 君选择第 $ 5 $ 块蛋糕，这块蛋糕的大小为 $ 9 $；
4. IOI 酱选择第 $ 4 $ 块蛋糕，这块蛋糕的大小为 $ 10 $；
5. JOI 君选择第 $ 3 $ 块蛋糕，这块蛋糕的大小为 $ 1 $；
最后 JOI 君得到的蛋糕的大小的总和为 $ 8+9+1=18 $。
#### 输入样例 2
```plain
8
1
10
4
5
6
2
9
3
```
#### 输出样例 2
```plain
26
```
#### 输入样例 3
```plain
15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789
```
#### 输出样例 3
```plain
3600242976
```
对于 $ 15\% $ 的分值：
- $ N \leq 20 $
对于另 $45\%$ 的分值：
- $ N \leq 300 $
对于 $100\%$ 的分值，所有输入数据满足以下条件：
- $ 1 \leq N \leq 2000 $；
- $ 1 \leq A_i \leq 10^9 $；
- 每个 $ A_i $ 都不同。
感谢@ミク 提供的翻译