CF1421E Swedish Heroes

在玩又一款策略游戏时，Mans 招募了 $n$ 位[瑞典英雄](https://www.youtube.com/watch?v=5sGOwFVUU0I)，他们的能力可以用一个数组 $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$ 次这样的操作后，Mans 最终只会剩下一个英雄。他希望这个英雄的能力尽可能大。请问他能获得的最大能力是多少？

第一行包含一个整数 $n$（$1 \le n \le 200000$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$），表示每位英雄的能力。

输出经过 $n-1$ 次操作后，Mans 能获得的最大能力。

对于第一个样例，合适的操作序列如下： $[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$。 由 ChatGPT 4.1 翻译