Swedish Heroes
Description
While playing yet another strategy game, Mans has recruited $n$ Swedish heroes, whose powers which can be represented as an array $a$.
Unfortunately, not all of those mighty heroes were created as capable as he wanted, so that he decided to do something about it. In order to accomplish his goal, he can pick two consecutive heroes, with powers $a_i$ and $a_{i+1}$, remove them and insert a hero with power $-(a_i+a_{i+1})$ back in the same position.
For example if the array contains the elements $[5, 6, 7, 8]$, he can pick $6$ and $7$ and get $[5, -(6+7), 8] = [5, -13, 8]$.
After he will perform this operation $n-1$ times, Mans will end up having only one hero. He wants his power to be as big as possible. What's the largest possible power he can achieve?
The first line contains a single integer $n$ ($1 \le n \le 200000$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — powers of the heroes.
Print the largest possible power he can achieve after $n-1$ operations.
Input
The first line contains a single integer $n$ ($1 \le n \le 200000$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — powers of the heroes.
Output
Print the largest possible power he can achieve after $n-1$ operations.
Samples
4
5 6 7 8
26
5
4 -5 9 -2 1
15
Note
Suitable list of operations for the first sample:
$[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$