「JOI 2014/2015 决赛」分蛋糕 2

译自 JOI 2014/2015 决赛 T2「ケーキの切り分け２」

题目描述

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 君得到的蛋糕大小的总和的最大值。

输入格式

第一行为整数 $N$ ，表示蛋糕被切成了 $N$ 块；
接下来 $N$ 行中的第 $i$ 行 $(1 \leq i \leq N)$ 为一个整数 $A_i$ 。表示第 $i$ 块蛋糕的大小。

输出格式

输出一行： JOI 君得到的蛋糕大小的总和的最大值。

样例

输入样例 1

5
2
8
1
10
9

输出样例 1

18

样例说明 1

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

8
1
10
4
5
6
2
9
3

输出样例 2

26

输入样例 3

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

输出样例 3

3600242976

数据范围

对于 $15\%$ 的分值：

• $N \leq 20$

对于另 $45\%$ 的分值：

• $N \leq 300$

对于 $100\%$ 的分值，所有输入数据满足以下条件：

• $1 \leq N \leq 2000$；
• $1 \leq A_i \leq 10^9$；
• 每个 $A_i$ 都不同。

感谢@ミク 提供的翻译