2709 「BalticOI 2015」黑客

题目译自 BalticOI 2015 Day2 Hacker(HAC)，原题面见附加文件。
如欲转载翻译，请注明翻译者信息及转载出处。

黑客 Byteasar 获得了参加今年 IHO，即国际黑客奥林匹克竞赛（International Hacker Olympiad）的机会。比赛的一个任务是与一个系统操作者对抗。有 $n$ 台从 $1$ 到 $n$ 编号的计算机，连接成了一个环，即编号为 $i$ 的计算机与编号为 $i+1$ 的计算机相连（对于 $i=1,2,3,\cdots,n-1$），编号为 $n$ 的计算机与编号为 $1$ 的计算机相连。 这场比赛以一个系统操作者与黑客的游戏进行。 + Byteasar 先操作，之后，系统操作者和 Byteasar 交替操作； + 第一次操作时，Byteasar 可以选择任一计算机然后黑掉它（例如，找寻一些操作系统的漏洞）； + 第一次操作时，操作者可以选择任一没有被黑的电脑，然后保护它（例如，安装最新的安全更新）； + 在所有接下来的操作中，Byteasar 要么什么都不做 （a），要么选择既没有被黑也没有被保护，同时和被黑的电脑直接相连的电脑（b），然后黑掉它； + 在所有接下来的操作中，操作者要么什么都不做（a），要么选择既没有被黑也没有被保护，同时和被保护的电脑直接相连的电脑（b），然后保护它； + 当双方在相邻的两个操作中都选择什么都不做，这个游戏结束。

在游戏开始，没有电脑被黑，也没有电脑被保护。

每台电脑都有一个特定的价值 $v_i$，表示存储在其中的数据的价值。对于每一个被黑的电脑 $i$，Byteasar 获得它的价值 $v_i$ 分。Byteasar 是一个十分出色的黑客，但是他不会算法。这就是他请你写一个程序去计算他的最大可能得分的原因。假设系统操作者永远采用最佳策略。

输入的第一行包含一个正整数 $n$，表示计算机台数。第二行是一个 $n$ 个正整数的序列 $v_i$，$v_i$ 表示计算机 $i$ 上存储的数据价值。

一行一个整数，表示 Byteasar 获得的最大可能得分。

第一个样例中，Byteasar 第一个黑掉的电脑是 $2$ 号（获得 $6$ 分）。作为回应，系统操作者会保护电脑 $3$。在接下来的操作中，Byteasar 会黑点电脑 $1$（获得 $7$ 分）。最后，操作者会保护电脑 $4$。

详见附加文件 hac_sample2.in/ans。

本题采用子任务式测评，只有一个子任务内所有测试点均正确才可获得此子任务的分数。

对于全部子任务，$n\ge 2,1\le v_i\le 2\times 10^3$。

对于每个子任务满足的条件如下：