一排有 $ n $ 个史莱姆。每个史莱姆都有一个整数值表示分数（可能为负或零）。 任何史莱姆都可以吃它相邻的史莱姆（在其左侧或右侧最近的史莱姆，假设该史莱姆存在）。 当一个具有值 $x$ 的史莱姆吃掉一个值为 $y$ 的史莱姆时，被吃掉的史莱姆消失，剩余的史莱姆的值会变为 $x - y$。 这些史莱姆会相互吃掉，直到最后只剩下一个史莱姆。 找到最后一个史莱姆可能的最大值。

第一行一个整数$n$ ($ 1 \le n \le 500\,000 $)
第二行$n$个整数，表示史莱姆的分数 ($ -10^9 \le a_i \le 10^9 $)

一个整数，即最大分数

### 样例输入 #2
5
0 -1 -1 -1 -1
### 样例输出 #2
4
用较快的输入输出方式：
关闭cin和cout同步：ios::sync_with_stdio(false)

cin.tie(0)表示使cin不与任何流绑定，防止cin的输入被复制到其他流中，提高cin的输入效率。

cout.tie(0)表示使cout不与任何流绑定，防止cout的输出被复制到其他流中，提高cout的输出效率。

 2022级ACM集训队选拔赛（3）