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 the possibility of winning a much larger sum of money. You have 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. 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.

Your task is to find the strategy that yields the highest amount of money.

Input

The first line contains a single number, N. The second line contains N numbers, C_1,\,C_2,\ldots,\,C_N, separated by spaces.

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

All values C_i are nonnegative integers.

Output

Print a single number, X, which is the highest possible amount of money in euros that you can obtain.

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 as red, black, red, green, black, green (in this order, starting with sector 1). In this way, you gain 1000 + 1024 euros and lose 1 + 2 euros, for a total net gain of 2021 euros.