Wine Tasting

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.

1. If a glass is chosen, all wine in that glass must be drunk, and the glass is then put back in its original position.
2. 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.

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.

Print the maximum amount of wine that can be drunk.