一排有 $$$n$$$ 史莱姆。每个粘液都有一个与之相关的整数值(可能是负数或零)。
任何史莱姆都可以吃掉其相邻的史莱姆(假设该史莱姆存在,则最接近其左侧或右侧的史莱姆)。
当值为 $$$x$$$ 的史莱姆吃了一个值为 $$$y$$$ 的史莱姆时,吃掉的史莱姆就会消失,剩余的史莱姆的值会变为 $$$x - y$$$。
史莱姆会互相吞噬,直到只剩下一个史莱姆。
找到最后一个史莱姆的最大可能值。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500\,000$$$) 表示史莱姆的数量。
下一行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个史莱姆的值。
输出
打印一个唯一的整数——最后一个粘液的最大可能值。
示例
输入 #1
4 2 1 2 1
输出 #1
4
输入 #2
5 0 -1 -1 -1 -1
输出 #2
4
注意
在第一个示例中,获取最后一个值为 $$$4$$$ 的粘液的可能方法是:
- 第二个史莱姆吃了第三个史莱姆,该行现在包含史莱姆 $$$2, -1, 1$$$
- 第二个史莱姆吃了第三个史莱姆,该行现在包含史莱姆 $$$2, -2$$$
- 第一个史莱姆吃了第二个史莱姆,该行现在包含 $$$4$$$
在第二个示例中,第一个史莱姆可以继续吃右侧的史莱姆,最终得到 $$$4$$$ 的值。