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.