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 翻译