You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

战争（$\texttt{war}$）

【题目描述】

在大陆上有 $n$ 个城市，他们排成一个环，第 $i$ 座城市与第 $i+1$ 座城市相邻，第 $n$ 座城市与第 $1$ 座城市相邻。

第 $i$ 个国家有重要程度 $a_i$，每个国家初始都未被占领。

现在 A 国和 B 国开战了，战争会持续若干天，每天按顺序会发生如下的事情：

• 如果当前有未被占领的城市，那么 A 国任选一个占领，如果此前有被 A 国占领的城市，那么此次选择的城市至少要和一个 A 国已占领的城市相邻。
• 如果当前有未被占领的城市，那么 B 国任选一个占领，如果此前有被 B 国占领的城市，那么此次选择的城市至少要和一个 B 国已占领的城市相邻。

任何时候双方都知道对面所有的决策，双方都想最大化自己占领城市的重要程度之和，且双方都采取最优策略。

小 D 想知道最终 A 国占领城市的重要程度之和是多少。

【输入格式】

从 $\texttt{war.in}$ 中读入数据。

第一行一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

【输出格式】

输出到 $\texttt{war.out}$ 中。

一行一个整数表示答案。

【样例 1 输入】

4
7 6 8 4

【样例 1 输出】

13

【样例 1 解释】

最优策略如下：A 国占领城市 $2$，B 国占领城市 $3$，A 国占领城市 $1$，B 国占领城市 $4$。

【样例 2】

见下发文件中的 $\texttt{war2.in}$ 与 $\texttt{war2.ans}$。

该样例满足子任务 $3$ 的限制。

【样例 3】

见下发文件中的 $\texttt{war3.in}$ 与 $\texttt{war3.ans}$。

该样例满足子任务 $4$ 的限制。

【数据范围】

对于所有测试数据有：$2\le n\le 5\times 10^5,1\le a_i\le 2000$。

特殊性质 $\text{A}$：存在一种最优策略使得 A 国第一天占领城市 $1$。