分蛋糕 2
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

JOI君和IOI酱是双胞胎兄妹。JOI君最近闲暇时常常会做甜点。今天JOI君也烤了蛋糕吃，IOI酱立马嗅到了蛋糕的香气于是跑来想分着吃。
蛋糕是圆形的，从蛋糕中某点开始将蛋糕放射状切为N块，按逆时针顺序编号为1到N。切了之后的第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行为一个整数A_i。表示第i块蛋糕的大小。

输出描述:

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

输入

复制 
5
2
8
1
10
9

输出

复制 
18

说明

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

输出

复制 
26
示例3

输入

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

输出

复制 
3600242976

备注:

对于所有数据，每个A_i都不同。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2725