说明

JOI 君和 IOI 酱是双胞胎兄妹。JOI 君最近沉迷于制作点心，今天他又烤了一个蛋糕准备自己吃，但蛋糕刚出炉时，IOI 酱闻着香味就来了，于是两人决定分享这个蛋糕。

蛋糕是圆形的。从某一点开始沿放射状切出切口，将蛋糕切成了 $N$ 块，并按逆时针方向给这些块依次编号为 $1$ 到 $N$。也就是说，对于 $1 \le i \le N$，第 $i$ 块与第 $i-1$ 块和第 $i+1$ 块相邻（这里认为第 $0$ 块是第 $N$ 块，第 $N+1$ 块是第 $1$ 块）。第 $i$ 块的大小是 $A_i$，但由于切蛋糕的技术很差，所有的 $A_i$ 值都互不相同。

:::align{center}

图 1: 蛋糕示例 ($N = 5, A_1 = 2, A_2 = 8, A_3 = 1, A_4 = 10, A_5 = 9$) :::

他们决定按以下规则来分配这 $N$ 块蛋糕：

1. 首先，由 JOI 君从 $N$ 块中任意选择一块取走。
2. 然后，从 IOI 酱开始，IOI 酱和 JOI 君轮流从剩余的块中每次取走一块。但是，只能取走至少有一侧相邻的块已经被取走的块。当有多个块可以取时，IOI 酱必须选择其中最大的一块取走，而 JOI 君可以选择其中任意一块取走。

JOI 君希望最大化他自己最终取到的所有块的大小之和。

任务

给定蛋糕的块数 $N$ 以及 $N$ 块蛋糕的大小信息，请编写一个程序，计算 JOI 君能取到的块的大小之和的最大值。

输入格式

从标准输入读取以下输入。

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

输出格式

向标准输出输出一行，包含一个整数，表示 JOI 君能取到的块的大小之和的最大值。

5
2
8
1
10
9

18

8
1
10
4
5
6
2
9
3

26

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

3600242976

提示

样例解释 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$。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 2000$。
• $1 \le A_i \le 1000000000$。
• 所有的 $A_i$ 互不相同。

子任务

子任务 1 [15 分]

• 满足 $N \le 20$。

子任务 2 [45 分]

• 满足 $N \le 300$。

子任务 3 [40 分]

没有额外限制。

翻译由 DeepSeek V3.2 完成