题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

样例 1

输入

4
1
2
3
4

输出

9

样例 2

输入

6
3
-2
-1
0
-1
4

输出

6

样例 3

输入

10
-84
-60
-41
-100
8
-8
-52
-62
-61
-76

输出

0

说明/提示

限制条件

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