题目描述

太郎和次郎之间要进行以下游戏。

一开始，他们得到一个序列 $a = (a_1, a_2, \ldots, a_N)$。在序列 $a$ 变为空之前，两个玩家轮流执行以下操作，从太郎开始：

• 删除 $a$ 的开头或末尾的元素。玩家获得被删除的元素作为分数，记为 $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$ 的结果值。

---

示例输入 1

4
10 80 90 30

示例输出 1

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$。

---

示例输入 2

3
10 100 10

示例输出 2

-80

当两个玩家采取最优策略时，游戏执行如下：

• 太郎: (10, 100, 10) → (100, 10)
• 次郎: (100, 10) → (10)
• 太郎: (10) → ()

此时，$X = 10 + 10 = 20$，$Y = 100$。

---

示例输入 3

1
10

示例输出 3

10

---

示例输入 4

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

示例输出 4

4999999995

结果可能不适合32位整数类型。

---

示例输入 5

6
4 2 9 7 1 5

示例输出 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$。