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.

Input

Input is given from Standard Input in the following format:
N
a_1
a_2
:
a_N

Output

Print the answer.

Constraints

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

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

见题面 Input 部分

见题面 Output 部分