T823228 蛋糕轮取（cake）

小明和小华准备分享一个圆形蛋糕。蛋糕已经沿径向切成了 $N$ 块，按逆时针方向依次编号为 $1,2,\ldots,N$。第 $1$ 块与第 $N$ 块也相邻。第 $i$ 块的大小为 $A_i$，所有蛋糕块的大小互不相同。 两人按照以下规则取走蛋糕： 1. 小明先从全部蛋糕块中任选一块取走。 2. 接下来，由小华开始，两人交替各取走一块，直到所有蛋糕都被取完。 3. 除了第一次取块以外，只能取走至少有一侧相邻蛋糕块已经被取走的块。 4. 轮到小华时，他总是取走当前可以取走的蛋糕块中较大的一块；轮到小明时，他可以任选当前允许取走的一块。 小明想让自己最终取走的蛋糕块大小之和尽量大。请计算这个最大值。

第一行包含一个正整数 $N$。 接下来 $N$ 行，第 $i$ 行包含一个正整数 $A_i$。

输出一行一个整数，表示小明最终能取得的蛋糕块大小之和的最大值。

### 样例解释 小明首先取走第 $2$ 块，大小为 $8$。此时可以取走第 $1$ 块和第 $3$ 块，小华取走较大的第 $1$ 块，大小为 $2$。 接下来，小明取走第 $5$ 块，大小为 $9$；小华取走第 $4$ 块，大小为 $10$；小明最后取走第 $3$ 块，大小为 $1$。 小明获得的总大小为 $8+9+1=18$，这是能够取得的最大值。 ## 样例 2 见 `考生目录/cake/cake2.in` 与 `考生目录/cake/cake2.ans`。该样例满足测试点 $1\sim3$ 的约束。 ## 样例 3 见 `考生目录/cake/cake3.in` 与 `考生目录/cake/cake3.ans`。该样例满足测试点 $4\sim12$ 的约束。 ## 样例 4 见 `考生目录/cake/cake4.in` 与 `考生目录/cake/cake4.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 样例 5 见 `考生目录/cake/cake5.in` 与 `考生目录/cake/cake5.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 样例 6 见 `考生目录/cake/cake6.in` 与 `考生目录/cake/cake6.ans`。该样例满足测试点 $1\sim3$ 的约束。 ## 数据范围 对于所有数据，保证 $1\le N\le2000$，$1\le A_i\le10^9$，且所有 $A_i$ 互不相同。 | 测试点编号 | 附加限制 | | ---------- | --------- | | $1\sim3$ | $N\le20$ | | $4\sim12$ | $N\le300$ | | $13\sim20$ | 无 |