[AGC050B] 三枚硬币

题目描述

有N个格子排成一列，从左到右依次编号为1到N。

初始时所有格子都是空的。你可以按任意顺序无限次进行以下两种操作：

• 选择连续的3个未放置硬币的格子，在每个格子中放置一枚硬币。
• 选择连续的3个都放置了硬币的格子，从每个格子中移除一枚硬币。

操作结束后，若从左数第i个格子中有硬币，则获得aᵢ分。所有有硬币的格子的得分总和即为你的总得分。

请求出能获得的最高得分。

输入格式

输入通过标准输入按以下形式给出：

N a₁ a₂ : aₙ

输出格式

输出答案。

输入输出样例 #1

输入 #1

4
1
2
3
4

输出 #1

9

输入输出样例 #2

输入 #2

6
3
-2
-1
0
-1
4

输出 #2

6

输入输出样例 #3

输入 #3

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

输出 #3

0

说明/提示

限制条件

• 3 ≤ N ≤ 500
• -100 ≤ aᵢ ≤ 100
• 输入中的所有值均为整数

样例解释 1

用o表示有硬币的格子，.表示空格子。一个最优操作流程如下：.... → .ooo，此时得分是2 + 3 + 4 = 9分。

样例解释 2

一个最优操作流程如下：...... → ooo... → oooooo → o...oo，此时得分是3 + (-1) + 4 = 6分。