Double Flip

Description

There is an array $A$ of length $N$, where $N$ is even. In one operation, you can partition the array into two (non-empty) parts and reverse those two parts. More formally, we choose an index $i$ ($1 \le i \lt N$) then we change the array into $[A_i, A_{i-1}, \ldots, A_1, A_N, A_{N-1}, \ldots, A_{i+1}]$.

Define the cost of the array as $\sum\limits_{i=1}^N (-1)^{i+1} A_i = A_1-A_2+A_3-A_4+\ldots-A_{N}$.

Find the maximum cost of the array after some (possibly zero) operations.

Constraints

• $2 \le N \le 100\;000$
• $-10^9 \le A_i \le 10^9$
• $N$ is even.

Input

N
A1 A2 … AN

Output

An integer representing the maximum cost.

Sample Input 1

2
123 456

Sample Output 1

-333

Sample Input 2

4
-1 1 -1 1

Sample Output 2

4

Explanation

In the first sample, $A = [123, 456]$. Since $N=2$, the only valid operation is using $i=1$, but after performing this operation, the array is unchanged. So the maximum cost of the array is $123-456=-333$.

In the second sample, $A = [-1, 1, -1, 1]$. After performing an operation with $i = 2$, the array becomes $[1, -1, 1, -1]$. The final cost of the array is $1 - (-1) + 1 - (-1) = 4$ and we can show that this is the maximum possible cost.