#P2067. Yougth'sGame[Ⅲ]

Yougth'sGame[Ⅲ]

有一个长度为n的整数序列,A和B轮流取数,A先取,每次可以从左端或者右端取一个数,所有数都被取完时游戏结束,然后统计每个人取走的所有数字之和作为得分,两人的策略都是使自己的得分尽可能高,并且都足够聪明,求A的得分减去B的得分的结果。

Input

输入包括多组数据,每组数据第一行为正整数n(1<=n<=1000),第二行为给定的整数序列Ai(-1000<=Ai<=1000)。

Output

对于每组数据,输出A和B都采取最优策略的情况下,A的得分减去B的得分的结果。

Sample Input

3
1 2 3
4
2 4 5 3

Sample Output

2
0

HINT

Source