Description

题面描述

Byteasar 获得了今年国际黑客奥林匹克竞赛的参赛资格。竞赛的任务之一是与系统操作员竞争。有从 $1$ 到 $n$ 编号的 $n$ 台计算机，以环形连接，即计算机 $i$ 和 $i+1$ 连接（其中 $i = 1,2,\dots,n-1$），特别的，计算机 $n$ 和 $1$ 也连接。

这个任务是黑客和系统操作员之间的游戏：

• Byteasar 先走。之后，操作员和 Byteasar 交替移动。
• Byteasar 的第一步是选择任何一台计算机并对其进行黑客攻击。
• 在他的第一步中，操作员选择任何未被黑客攻击的计算机并对其进行保护。
• 在接下来的所有动作中，Byteasar 要么什么都不做，要么选择任意一台既没有被黑客攻击也没有受到保护的计算机且该计算机直接链接到任意一台被黑客攻击的计算机，然后对其进行黑客攻击。
• 在接下来的所有动作中，操作员要么什么都不做，要么选择任意一台既没有被黑客攻击也没有受到保护的计算机且该计算机直接链接到任何受保护的计算机并对其进行保护。
• 一旦两人在接下来的两个动作中都没有做任何事情，游戏就结束了。

在游戏开始时，没有任何一台电脑被黑客攻击或受到保护。

每台计算机 $i$ 都有一个特定的值 $v_i$，该值指定了存储在这台电脑上的数据的价值。Byteasar 最终获得的分数就是所有被他攻击的计算机的 $v$ 值之和。

虽然 Byteasar 是一个很好的黑客，但对算法一无所知——这就是为什么他要求你编写一个程序来计算他的最大的可能分数，假设操作员按最优策略进行操作。

Input Format

第一行输入包含一个正整数 $n(n\ge 2)$，指定计算机的数量。第二行包含一个含有 $n$ 个整数的序列 $v_1,v_2,\dots,v_n(1\le v_i\le 2000)$。

Output Format

在输出的第一行，也是唯一一行，你的程序应该输出一个整数：Byteasar 获得的总得分的最大值。

4
7 6 8 4

13

5
1 1 1 1 1

3

Hint

对样例的说明：

在第一个样例中，Byteasar 应在第一步黑客攻击编号为 $2$ 的计算机（得分为 $6$）。系统操作员第二步选择保护编号为 $3$ 的计算机。接下来 Byteasar 选择黑客攻击编号为 $1$ 的计算机（得分为 $7$）。最后，系统操作员选择保护编号为 $4$ 的计算机。由于双方都不能继续操作，游戏结束。最后 Byteasar 的得分为 $13$，可以证明这是他的最大得分。

数据范围：

对于 $100\%$ 的数据，满足 $2 \le n \le 5 \times 10^5,1\le v_i\le 2000$。