2079: Slime
[Creator : ]
Description
一排有 $ n $ 个史莱姆。每个史莱姆都有一个整数值表示分数（可能为负或零）。
任何史莱姆都可以吃它相邻的史莱姆（在其左侧或右侧最近的史莱姆，假设该史莱姆存在）。
当一个具有值 $x$ 的史莱姆吃掉一个值为 $y$ 的史莱姆时，被吃掉的史莱姆消失，剩余的史莱姆的值会变为 $x - y$。
这些史莱姆会相互吃掉，直到最后只剩下一个史莱姆。
找到最后一个史莱姆可能的最大值。
Input
第一行一个整数$n$ ($ 1 \le n \le 500\,000 $)
第二行$n$个整数，表示史莱姆的分数 ($ -10^9 \le a_i \le 10^9 $)
第二行$n$个整数，表示史莱姆的分数 ($ -10^9 \le a_i \le 10^9 $)
Output
一个整数，即最大分数
Sample Input Copy
4
2 1 2 1
Sample Output Copy
4
HINT
### 样例输入 #2
5
0 -1 -1 -1 -1
### 样例输出 #2
4
用较快的输入输出方式：
关闭cin和cout同步：ios::sync_with_stdio(false)
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的输出效率。