CF1038D.Slime

There are $n$ slimes in a row. Each slime has an integer value (possibly negative or zero) associated with it.

Any slime can eat its adjacent slime (the closest slime to its left or to its right, assuming that this slime exists).

When a slime with a value $x$ eats a slime with a value $y$, the eaten slime disappears, and the value of the remaining slime changes to $x - y$.

The slimes will eat each other until there is only one slime left.

Find the maximum possible value of the last slime.

一行中有 $n$ 个史莱姆。每个史莱姆都关联一个整数值（可能为负数或零）。

任意一个史莱姆都可以吃掉其相邻的史莱姆（即其左侧或右侧最近的一个史莱姆，前提是该史莱姆存在）。

当一个值为 $x$ 的史莱姆吃掉一个值为 $y$ 的史莱姆时，被吃的史莱姆消失，剩余史莱姆的值变为 $x - y$。

史莱姆将持续互相吞食，直到仅剩一个史莱姆为止。

求最后一个史莱姆可能的最大值。

The first line of the input contains an integer $n$ ($1 \le n \le 500\,000$) denoting the number of slimes.

The next line contains $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$), where $a_i$ is the value of $i$-th slime.

输入的第一行包含一个整数 $n$（$1 \le n \le 500\,000$），表示史莱姆的数量。

第二行包含 $n$ 个整数 $a_i$（$-10^9 \le a_i \le 10^9$），其中 $a_i$ 表示第 $i$ 个史莱姆的值。

Print an only integer — the maximum possible value of the last slime.

输出一个整数——最后一个史莱姆可能的最大值。

In the first example, a possible way of getting the last slime with value $4$ is:

• Second slime eats the third slime, the row now contains slimes $2, -1, 1$
• Second slime eats the third slime, the row now contains slimes $2, -2$
• First slime eats the second slime, the row now contains $4$

In the second example, the first slime can keep eating slimes to its right to end up with a value of $4$.

在第一个例子中，得到最后一只值为 $4$ 的史莱姆的一种可能方式是：

• 第二只史莱姆吃掉第三只史莱姆，此时序列变为史莱姆 $2, -1, 1$；
• 第二只史莱姆吃掉第三只史莱姆，此时序列变为史莱姆 $2, -2$；
• 第一只史莱姆吃掉第二只史莱姆，此时序列变为 $4$。

在第二个例子中，第一只史莱姆可以持续吃掉其右侧的史莱姆，最终得到值为 $4$ 的史莱姆。