In the city of Oopse there are many casinos. One of the casinos, namely The Great Wave, has the following game: The dealer deals n cards number side up on a row. Each turn player picks three consecutive cards with number side up, flips them and gains points equal to the number denoted in the midmost card. The game ends when there are no three consecutive cards that are number side up. The player tries to maximize their points.

Your task is to find out the maximum number of points in the given game.

Input

The first line contains a single integer, n, the number of cards being dealt. The second line contains n integers, x_1,x_2,...x_n, the values denoted on the cards.

Output

Output a single integer, the maximum points the player can get in the game.

Limits

• 1 \le n \le 10^6
• 1 \le x_1,x_2,...x_n \le 10^3

Example

Input:

9
2 7 1 1 5 7 4 1 1

Output:

14

Explanation:

The player can first flip the cards 5,7,4 and gain 7 points. Then they can flip the cards 2,7,1 and gain another 7 points. Now the player is stuck and the game ends.