CF731E Funny Game

从前，Petya 和 Gena 在又一次编程比赛后聚在一起，决定玩个游戏。他们觉得大多数现代游戏都很无聊，所以总是自己发明游戏。他们只有贴纸和记号笔，但这并不会阻止他们。 他们发明的游戏规则如下。最开始，墙上有 $n$ 张贴纸按顺序排成一行。每张贴纸上写有一个整数。他们轮流行动，Petya 先手。 每一回合的操作如下。假设墙上当前有 $m \geq 2$ 张贴纸。轮到当前玩家时，他选择一个 $k$，满足 $2 \leq k \leq m$，然后取下最左边的 $k$ 张贴纸（从墙上移除）。之后，他会制作一张新贴纸，将其贴到队列最左端，并在上面写下他刚刚取下的所有贴纸上的整数之和。 当墙上只剩一张贴纸时，游戏结束。每个玩家的得分为他在整个游戏过程中拿下的所有贴纸上的数字之和。每个玩家都希望最大化自己的得分与对手得分的差值。 给定整数 $n$ 和初始贴纸序列，求游戏结果，即当双方都采取最优策略时，Petya 得分与 Gena 得分之差。

输入第一行包含一个整数 $n$（$2 \leq n \leq 200000$），表示墙上最初贴纸的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10000 \leq a_i \leq 10000$），表示从左到右每张贴纸上的数字。

输出一个整数，表示在双方都采取最优策略的情况下，Petya 得分减去 Gena 得分的最终结果。

在第一个样例中，Petya 最优的做法是直接拿走所有贴纸。因此，他的得分为 $14$，Gena 的得分为 $0$。 在第二个样例中，最优的操作序列如下。第一步 Petya 拿走前面三张贴纸，新贴纸数字为 $-8$。第二步 Gena 拿下剩下两张贴纸。Petya 得分为 $1+(-7)+(-2)=-8$，Gena 得分为 $(-8)+3=-5$，得分差为 $-3$。 由 ChatGPT 5 翻译