Wine Tasting

Interview

Time limit2sMemory limit128 MB

Summary

Pick numbers from a sequence maximizing sum while never selecting three consecutive elements.

Level: Medium5 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Hyoju sees n wine glasses arranged in a line at a wine tasting. Each glass contains a certain amount of wine. Hyoju wants to drink as much wine as possible while following these rules.

If a glass is chosen, all wine in that glass must be drunk, and the glass is then put back in its original position.
It is not allowed to choose all of any 3 consecutive glasses.

Given the amount of wine in each glass from left to right, write a program that finds the maximum amount of wine Hyoju can drink.

Input

The first line contains the number of wine glasses n. (1 ≤ n ≤ 10,000)

Each of the next n lines contains the amount of wine in one glass, in order. Each amount is a nonnegative integer not greater than 1,000.

Output

Print the maximum amount of wine that can be drunk.

Examples1

Example 1
Input
```
6
6
10
13
9
8
1
```
Expected output
```
33
```