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 是一个很好的黑客，但对算法一无所知——这就是为什么他要求你编写一个程序来计算他的最大可能分数，假设操作员按最优策略。

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

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

BalticOI 2015