题目描述

一天，Aki在追讨恶龙的过程中，不小心中了女巫的陷阱，被女巫带到了她的城堡里。女巫并不坏，但她十分聪明，由于女巫平时太无聊了，她告诉Aki，如果能在游戏上让她感受到挑战，就能获得自由，并获得女巫的奖励——飞行扫帚。

游戏开始前，女巫把n张自制塔罗牌从左到右排列在桌子上，每张塔罗牌上面都有一个数字。游戏是回合制，两人轮流行动，由Aki先开始。每个人都可以在自己的回合从这组牌的最左侧或者最右侧挑一张牌，然后把选到数字加入自己的得分。当牌都被取完时，游戏结束。

设Aki的最终得分为X，女巫的最终得分为Y，Aki想让X-Y的结果尽量的大，而女巫想让X-Y的结果尽量的小。现在请问，两人都采用最优策略的情况下，最后X-Y的结果是多少？

输入格式

第一行一个数n，代表牌的数量 第二行n个数，代表每张牌上的数字

对于100%的数据，保证$n<=3000, 1<=a[i]<=10^9$

输出格式

一个数，代表最终X-Y的结果。

4
10 80 90 30

10

Hint

样例解释： Aki: (10, 80, 90, 30) → (10, 80, 90) 女巫: (10, 80, 90) → (10, 80) Aki: (10, 80) → (10) 女巫: (10) → ()

X=30+80=110 Y=90+10=100 X-Y=10