Description

熊大和熊二将进行以下比赛。

最初，它们被赋予序列 $a=(a_1,a_2,…,a_N)$。直到 $a$ 变空，两名大佬交替执行以下操作，从熊大开始：

移除 $a$ 开头或结尾的元素。玩家获得 $x$ 点，其中 $x$ 是移除的元素。

让 $X$ 和 $Y$ 分别是熊大和熊二在比赛结束时的总分。熊大试图最大化 $X−Y$，而熊二试图最小化 $X−Y$。

假设两名大佬都最佳发挥，找到最终的 $X-Y$。

Input

输入格式如下：

$N\\a_1\ a_2\ …a_N$

输入中的所有值都是整数。 $1≤N≤3000\\1≤a_i≤10^9$ ​

Output

假设两个玩家都玩出最佳策略，输出最终的 $X-Y$。

Samples

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

答案可能超出32位整数类型。

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