← 返回题目列表

Codeforces · 1421/E

E. 瑞典英雄

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

在玩另一款策略游戏时,Mans 招募了 $$$n$$$ 瑞典英雄,他们的力量可以用数组 $$$a$$$ 表示。

不幸的是,并不是所有这些强大的英雄都具有他想要的能力,因此他决定为此做点什么。为了实现他的目标,他可以选择两个连续的英雄,力量为 $$$a_i$$$ 和 $$$a_{i+1}$$$,将其删除,然后将力量为 $$$-(a_i+a_{i+1})$$$ 的英雄放回到同一位置。

例如,如果数组包含元素$$$[5, 6, 7, 8]$$$,他可以选择$$$6$$$和$$$7$$$并得到$$$[5, -(6+7), 8] = [5, -13, 8]$$$。

在执行此操作 $$$n-1$$$ 次后,Mans 最终将只剩下一名英雄。他希望自己的权力尽可能的大。他能达到的最大力量是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 英雄的力量。

输出

打印他在 $$$n-1$$$ 操作后可以达到的最大可能功率。

示例

输入 #1

4
5 6 7 8

输出 #1

26

输入 #2

5
4 -5 9 -2 1

输出 #2

15

注意

第一个样本的合适操作列表:

$$$[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$$$