题目描述

$N$ 個のマスが一列に並んでおり、左から右に $1$ から $N$ までの番号が振られています。

はじめ、すべてのマスは空です。 あなたは、以下の $2$ 種類の操作を任意の順に何度でも行うことができます。

• 連続する $3$ マスであってコインが置かれていないものを選び、それぞれにコインを置く。
• 連続する $3$ マスであっていずれにもコインが置かれているものを選び、それぞれからコインを取り除く。

操作を済ませた後、左から $i$ マス目にコインが置かれているなら、$a_i$ 点が得られます。 コインがあるマス全てから得られる点数の合計が、あなたの得点です。

得られる最高得点を求めてください。

输入格式

入力は標準入力から以下の形式で与えられる。

$N$ $a_1$ $a_2$ $:$ $a_N$

输出格式

答えを出力せよ。

题目大意

有 $n$ 个盒子排成一列，从左到右分别编号为 $1\sim n$。

最开始，每个盒子都是空的。你可以以任何顺序进行如下两种操作任意次：

• 选择三个连续的空盒子，向其中分别放入一枚硬币。
• 选择三个连续的放有硬币的盒子，取出其中的硬币。

操作完后，假设第 $i$ 个盒子中装有硬币，你会获得 $a_i$ 分。最终分数是你从各个盒子处获得的分数的和。

请输出最终分数的最大值。

$3\le n\le 500, \ -100\le a_i \le 100$。

4
1
2
3
4

9

6
3
-2
-1
0
-1
4

6

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

0

提示

制約

• $3\ \leq\ N\ \leq\ 500$
• $-100\ \leq\ a_i\ \leq\ 100$
• 入力中の全ての値は整数である。

Sample Explanation 1

コインが置かれたマスを o で、置かれていないマスを . で表します。 最適な手順の $1$ つは次の通りです。 .... $\rightarrow$ .ooo このようにすれば、$2\ +\ 3\ +\ 4\ =\ 9$ 点を得られます。

Sample Explanation 2

最適な手順の $1$ つは次の通りです。 ...... $\rightarrow$ ooo... $\rightarrow$ oooooo $\rightarrow$ o...oo このようにすれば、$3\ +\ (-1)\ +\ 4\ =\ 6$ 点を得られます。