CF1421E.Swedish Heroes

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?

在玩另一款策略游戏时，曼斯招募了 $n$ 位瑞典英雄，他们的能力值可用一个数组 $a$ 表示。

不幸的是，并非所有这些强大的英雄都如他所愿般强大，因此他决定对此做些改进。为达成目标，他可以任选两个相邻的英雄，其能力值分别为 $a_i$ 和 $a_{i+1}$，将他们移除，并在同一位置插入一位新英雄，其能力值为 $-(a_i+a_{i+1})$。

例如，若数组为 $[5, 6, 7, 8]$，他可选取 $6$ 和 $7$，从而得到 $[5, -(6+7), 8] = [5, -13, 8]$。

在执行该操作 $n-1$ 次后，曼斯最终将只剩一位英雄。他希望这位英雄的能力值尽可能大。那么，他所能达到的最大能力值是多少？

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.

第一行包含一个整数 $n$（$1 \le n \le 200000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）——英雄们的力量值。

Print the largest possible power he can achieve after $n-1$ operations.

输出经过 $n-1$ 次操作后他所能达到的最大可能能量值。

Suitable list of operations for the first sample:

$[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$

第一个样例的可行操作序列：

$[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$