B - Three Coins Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800

問題文

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

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

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

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

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

制約

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

入力

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

N
a_1
a_2
:
a_N

出力

答えを出力せよ。


入力例 1

4
1
2
3
4

出力例 1

9

コインが置かれたマスを o で、置かれていないマスを . で表します。 最適な手順の 1 つは次の通りです。

.... \rightarrow .ooo

このようにすれば、2 + 3 + 4 = 9 点を得られます。


入力例 2

6
3
-2
-1
0
-1
4

出力例 2

6

最適な手順の 1 つは次の通りです。

...... \rightarrow ooo... \rightarrow oooooo \rightarrow o...oo

このようにすれば、3 + (-1) + 4 = 6 点を得られます。


入力例 3

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

出力例 3

0

Score : 800 points

Problem Statement

N cells are arranged in a row. The cells are numbered 1 through N from left to right.

Initially, all cells are empty. You can perform the following two types of operation arbitrary number of times in arbitrary order:

  • Choose three consecutive empty cells, and put a coin on each of the three cells.
  • Choose three consecutive cells with coins, and remove all three coins on the chosen cells.

After you finish performing operations, if the i-th cell contains a coin, you get a_i points. Your score is the sum of all points you get from the cells with coins.

Compute the maximum possible score you can earn.

Constraints

  • 3 \leq N \leq 500
  • -100 \leq a_i \leq 100
  • All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1
a_2
:
a_N

Output

Print the answer.


Sample Input 1

4
1
2
3
4

Sample Output 1

9

We represent a cell with a coin as o and a cell without a coin as . (a dot). One optimal way is as follows:

.... \rightarrow .ooo

We get 2 + 3 + 4 = 9 points this way.


Sample Input 2

6
3
-2
-1
0
-1
4

Sample Output 2

6

One optimal way is as follows:

...... \rightarrow ooo... \rightarrow oooooo \rightarrow o...oo

We get 3 + (-1) + 4 = 6 points this way.


Sample Input 3

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

Sample Output 3

0