A54980.取石子（双端版）

太郎和二郎将进行以下博弈。

最初，他们面前有 $N$ 堆石子排成一排，每堆石子有 $a_i$ 个 。在取完所有石子之前，两位选手从太郎开始交替执行以下操作：

• 取走开头或结尾的一堆石子。选手获得 $x$ 分，其中 $x$ 是被移除的石子的个数。

假设 $X$ 和 $Y$ 分别是太郎和二郎在游戏结束时的总得分。太郎试图最大化 $X - Y$ ，而二郎试图最小化 $X - Y$ 。

假设两位选手的选法都是最优的，请求出 $X - Y$ 的结果值。

限制因素

• 所有输入值均为整数。
• $1 \leq N \leq 3000$
• $1 \leq a_i \leq 10^9$

输入内容由标准输入法提供，格式如下：

$N$
$a_1$ $a_2$ $\ldots$ $a_N$

打印 $X - Y$ 的结果值，假定两位选手以最佳方式取石子。