← 返回题目列表

Codeforces · 731/E

E. 有趣的游戏

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

很久以前,Petya 和 Gena 在另一场编程比赛后聚集在一起,决定玩一些游戏。由于他们认为大多数现代游戏都很无聊,因此他们总是尝试发明自己的游戏。他们只有贴纸和记号笔,但这并不能阻止他们。

他们想出的游戏有以下规则。最初,墙上有n张贴纸,排成一排。每个贴纸上都写有一些数字。现在他们轮流轮流,佩蒂亚先行动。

一个动作发生如下。假设墙上有 m ≥ 2 张贴纸。进行当前移动的玩家从 2 到 m 中选择一些整数 k 并拿走最左边的 k 个贴纸(将它们从墙上移除)。之后,他制作了新的贴纸,将其放在该行的左端,并在上面写下了新的整数,等于他在这一举动中所采取的所有贴纸的总和。

当墙上只剩下一张贴纸时游戏结束。玩家的分数等于他在所有动作中所采取的所有贴纸上写的整数之和。每个玩家的目标是最大化自己的得分与对手的得分之间的差异。

给定整数 n 和墙上贴纸的初始序列,定义游戏的结果,即,如果两个玩家都发挥最佳,Petya 和 Gena 的得分之间的差异。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 200 000) - 最初位于墙上的贴纸数量。

第二行包含 n 个整数 a1, a2, ..., an ( - 10 000 ≤ ai ≤ 10 000) — 贴纸上的数字,按从左到右的顺序排列。

输出

打印一个整数 - 如果两名玩家都发挥最佳状态,则比赛结束时 Petya 的得分与 Gena 的得分之间的差值。

示例

输入 #1

3
2 4 8

输出 #1

14

输入 #2

4
1 -7 -2 3

输出 #2

-3

注意

在第一个示例中,Petya 的最佳动作是拿走所有贴纸。结果,他的分数将等于 14,Gena 的分数将等于 0。

在第二个示例中,最佳移动顺序如下。第一步,Petya 将拿走前三个贴纸,并贴上价值为 8 的新贴纸。第二步,Gena 将拿走剩余的两张贴纸。 Petya 的得分为 1 + ( - 7) + ( - 2) = - 8,Gena 的得分为 ( - 8) + 3 = - 5,即得分差为 - 3。