← 返回题目列表

Codeforces · 1038/D

D. 史莱姆

中文机器翻译题面 查看原题

一排有 $$$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$$$ 的值。