### ** 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
A_{1} A_{2} … A_{N}

### 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.