问题陈述

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

最初，他们得到一个序列 $a = (a_1, a_2, \ldots, a_N)$ 。在 $a$ 变为空之前，两位棋手从太郎开始交替执行以下操作：

• 删除 $a$ 开头或结尾的元素。棋手获得 $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$ 的结果值，假定两位棋手以最佳方式下棋。

4
10 80 90 30

10

当两位棋手以最佳方式下棋时，博弈过程如下（被删除的元素用粗体字标出）：

• 太郎：（10，80，90，30）→（10，80，90）
• 二郎：（10，80，90）→（10，80）
• 太郎：（10、80）→（10）
• 二郎：（10）→（）。

这里是 $X = 30 + 80 = 110$ 和 $Y = 90 + 10 = 100$ 。

3
10 100 10

-80

例如，当两位棋手以最佳方式下棋时，博弈过程如下：

• 太郎：（10，100，10）→（100，10）
• 二郎：（100，10）→（10）
• 太郎：（10）→（）。

这里是 $X = 10 + 10 = 20$ 和 $Y = 100$ 。

1
10

10

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

4999999995

6
4 2 9 7 1 5

2

例如，当两位棋手以最佳方式下棋时，博弈过程如下：

• 太郎：（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$ 。

来源

https://atcoder.jp/contests/dp/tasks/dp_l