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.