黑客 Byteasar 获得了今年国际黑客奥林匹克竞赛（IHO）的参赛资格。竞赛的任务之一是与系统管理员进行对抗。共有 $n$ 台计算机编号为 $1$ 到 $n$，它们连接成环状拓扑结构，即计算机 $i$ 和 $i+1$ 相连（对于 $i = 1, \dots, n-1$），且计算机 $n$ 和 $1$ 也相连。

比赛在黑客和系统管理员之间进行： Byteasar 先手。之后，管理员和 Byteasar 交替行动。 在第一次行动中，Byteasar 选择任意一台计算机并将其黑入（例如，通过利用某些操作系统漏洞）。 在第一次行动中，管理员选择任意一台未被黑入的计算机并将其保护起来（例如，通过安装最新的安全更新）。 在随后的所有行动中，Byteasar 可以选择（a）什么都不做，或者（b）选择任意一台既未被黑入也未被保护，且与任何已黑入计算机直接相连的计算机，并将其黑入。 在随后的所有行动中，管理员可以选择（a）什么都不做，或者（b）选择任意一台既未被黑入也未被保护，且与任何已保护计算机直接相连的计算机，并将其保护起来。 当双方在连续两次行动中都选择什么都不做时，游戏结束。

游戏开始时，没有任何计算机被黑入或保护。

每台计算机 $i$ 都有一个特定的值 $v_i$，表示存储在其上的数据价值。对于每台被黑入的计算机 $i$，Byteasar 获得其价值 $v_i$。Byteasar 是一名优秀的黑客，但对算法一窍不通。因此，他请求你编写一个程序，在假设管理员采取最优策略的情况下，计算他可能获得的最大分数。

输入格式

第一行包含一个正整数 $n$ ($n \ge 2$)，表示计算机的数量。第二行包含一个由 $n$ 个整数组成的序列 $v_1, v_2, \dots, v_n$ ($1 \le v_i \le 2000$)，数字 $v_i$ 表示存储在计算机 $i$ 上的数据价值。

输出格式

输出一行一个整数：在管理员采取最优策略的情况下，Byteasar 可能获得的最大分数。

样例

样例输入 1

4
7 6 8 4

样例输出 1

13

样例输入 2

5
1 1 1 1 1

样例输出 2

3

说明

在第一个样例中，Byteasar 在第一次行动中应黑入计算机 2（得分为 6）。管理员的应对措施是保护计算机 3。在下一次行动中，Byteasar 可以黑入计算机 1（得分为 7）。最后，管理员将保护计算机 4。

子任务