AT_agc050_b.[AGC050B] Three Coins

有 $N$ 个格子排成一行，从左到右编号为 $1$ 到 $N$。

开始时，所有格子都是空的。你可以任意顺序、任意次数地进行以下两种操作：

• 选择连续的 $3$ 个没有放置硬币的格子，在每个格子上放置一个硬币。
• 选择连续的 $3$ 个都已经放置了硬币的格子，从每个格子上移除一个硬币。

操作结束后，如果从左起第 $i$ 个格子上有硬币，你可以获得 $a_i$ 分。你最终得分为所有有硬币的格子的得分之和。

请你求出可以获得的最大得分。

输入从标准输入中读取，格式如下：

$N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出一个整数，表示可以获得的最大得分。

限制条件

• $3 \leq N \leq 500$
• $-100 \leq a_i \leq 100$
• 输入中的所有值均为整数。

样例解释 1

用 o 表示放置了硬币的格子，用 . 表示没有放置硬币的格子。最优的一种操作顺序如下：.... $\rightarrow$ .ooo。这样可以获得 $2 + 3 + 4 = 9$ 分。

样例解释 2

最优的一种操作顺序如下：...... $\rightarrow$ ooo... $\rightarrow$ oooooo $\rightarrow$ o...oo。这样可以获得 $3 + (-1) + 4 = 6$ 分。

由 ChatGPT 4.1 翻译