JOI 君和 IOI 酱是双胞胎兄妹。JOI 君最近热衷于制作点心，今天 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$ 互不相同。

图 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 君能拿到的部分的大小总和的最大值。

输入格式

从标准输入读取以下内容：

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

输出格式

将 JOI 君能拿到的部分的大小总和的最大值作为一个整数输出到标准输出。

数据范围

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

• $1 \le N \le 2000$
• $1 \le A_i \le 1\,000\,000\,000$
• $A_i$ 互不相同

子任务

1. (15 分) 满足 $N \le 20$。
2. (45 分) 满足 $N \le 300$。
3. (40 分) 无额外限制。

样例

样例输入 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