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

### Submitting .cpp to 'Double Flip'

Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 19