You are sitting in front of a roulette-style wheel with N sectors, and each sector is labeled with a sum of money.

Instead of spinning the wheel, the TV show host is offering you a possibility of winning a much larger sum of money. You have got black, red, and green tokens, and you have to place them on the sectors so that each sector gets one token and adjacent sectors have different colors. Now you will get money as follows:

For each black token you gain the sum of money in the sector.
For each red token you lose the sum of money in the sector.
The sectors with green tokens are ignored.
Now you need to find the strategy that gives the highest amount of money.

Input

First a line with one number, N. Then one line with N numbers, C_1,\,C_2,\ldots,\,C_N, separated by spaces.

These numbers indicate the sums of money that are there in each sector, in euros, in the clockwise order. For example, C_2 is the sum in the sector between C_1 and C_3, and C_N is the sector between C_{N-1} and C_1.

All values C_i are nonnegative integers.

Output

Print out one number, X, which is the highest possible amount of money in euros that you can get.

Constraints

• 3 \leq N \leq 10^5
• 0 \leq C_i \leq 10^5

Example

Input:

6
1 1000 2 3 1024 4

Output:

2021

Explanation:

You can label the 6 sectors with red, black, red, green, black, green (in this order, starting with sector 1), and this way gain 1000 + 1024 euros and lose 1 + 2 euros, with the total net gain 2021 euros.