配点: 100 点
JOI君和IOI酱是双胞胎兄妹。 JOI君最近开始热衷于烘焙,今天烤了一个蛋糕,正准备吃,结果烘焙完成后,IOI酱闻到了香味,走了过来。 2 决定把蛋糕分给大家。
蛋糕是圆形的。从某一点开始放射状切割并切蛋糕。 N 切成块; 逆时针编号至 1 到 N 。换句话说, 对于1 \leqq i \leqq N , 第i 块是 i - 1 th 和 它与 i + 1 块相邻(但是 0 th 是 N 番目,N + 1 th 是 1 )。i 块的大小是 A_i ,但我剪得非常不好,所以 A_i 都有不同的值。

这个 我决定将 N 碎片分给JOI君和IOI酱。我决定将其划分如下:
- 首先,JOI君。 N 最喜欢的作品 1 选择一项。
- 之后,IOI酱和JOI君轮流捡起剩下的棋子,从IOI酱开始。 1 一一拿走。不过,只能在双方至少有一个棋子已经被拿走的情况下拿走一颗棋子,如果有多个可以拿走的棋子,IOI-chan可以选择最大的一个并拿走它,而JOI-kun可以选择他喜欢的一个并拿走它。
JOI-kun 想要最大化他最终获得的棋子的总大小。
課題
蛋糕块数 N 和 编写一个程序,根据N 片段大小的信息,计算 JOI 可以占用的片段总大小的最大值。
入力
从标准输入读取以下输入。 写着
- 1 行是一个整数 N ,蛋糕是 表示它被切成 N 块。
- 继续 N 行 i 行目 (1 \leqq i \leqq N) 是一个整数 写入 A_i ,i 块的大小是 A_i 。
出力
表示 JOI-kun 可以拿走的最大棋子总尺寸的整数被发送到标准输出。 输出为 1 行。
制限
所有输入数据满足以下条件。
- 1 \leqq N \leqq 2\,000.
- 1 \leqq A_i \leqq 1\,000\,000\,000.
- A_i 都是不同的。
小課題
小課題 1 [15 点]
- N \leqq 20 满意。
小課題 2 [45 点]
- N \leqq 300 满意。
小課題 3 [40 点]
没有其他限制。
入力例 1
5 2 8 1 10 9
出力例 1
18
JOI君最好按如下方式拿走棋子。
- JOI-kunha 拿走第 2 块。这件作品的尺寸是 8 。
- IOI酱 1 块。这件作品的尺寸是 2 。
- JOI-kunha 拿走第 5 块。这件作品的尺寸是 9 。
- IOI酱 4 块。这件作品的尺寸是 10 。
- JOI-kunha 拿走第 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