AT_dp_l Deque

太郎君和次郎君进行如下游戏。 最初，给定一个数列 $a = (a_1, a_2, \ldots, a_N)$。两人轮流进行如下操作，直到 $a$ 变为空。太郎君先手。 - 可以移除 $a$ 的首元素或末元素。设移除的元素为 $x$，则执行操作的人获得 $x$ 分。 游戏结束时，太郎君的总得分为 $X$，次郎君的总得分为 $Y$。太郎君希望最大化 $X - Y$，次郎君则希望最小化 $X - Y$。 假设两人都采取最优策略，求 $X - Y$ 的值。

输入以如下格式从标准输入读入。 > $N$ $a_1$ $a_2$ $\ldots$ $a_N$

假设两人都采取最优策略，输出 $X - Y$ 的值。

## 限制条件 - 输入均为整数。 - $1 \leq N \leq 3000$ - $1 \leq a_i \leq 10^9$ ## 样例解释 1 两人采取最优策略时，操作过程如下。被操作的元素用粗体表示。 - 先手：（10, 80, 90, **30**）→（10, 80, 90） - 后手：（10, 80, **90**）→（10, 80） - 先手：（10, **80**）→（10） - 后手：（**10**）→（） 此时，$X = 30 + 80 = 110$，$Y = 90 + 10 = 100$。 ## 样例解释 2 两人采取最优策略时，操作过程例如如下。 - 先手：（**10**, 100, 10）→（100, 10） - 后手：（**100**, 10）→（10） - 先手：（**10**）→（） 此时，$X = 10 + 10 = 20$，$Y = 100$。 ## 样例解释 4 答案可能超出 32 位整数范围。 ## 样例解释 5 两人采取最优策略时，操作过程例如如下。 - 先手：（4, 2, 9, 7, 1, **5**）→（4, 2, 9, 7, 1） - 后手：（**4**, 2, 9, 7, 1）→（2, 9, 7, 1） - 先手：（2, 9, 7, **1**）→（2, 9, 7） - 后手：（2, 9, **7**）→（2, 9） - 先手：（2, **9**）→（2） - 后手：（**2**）→（） 此时，$X = 5 + 1 + 9 = 15$，$Y = 4 + 7 + 2 = 13$。 由 ChatGPT 4.1 翻译