严神被隔离久了很无聊, 于是发明了一种游戏。
给出一个数列 a, 甲乙两人每次从数列中拿取一个数,直到取完为止。 甲先手。获得的分数为每人取到所有数字的数字和。
现在严神想知道, 如果两人都按照最优策略取, 甲的分数比乙高多少。
输入共 2 行。
第 1 行, 一个整数 N , 代表数列 a 的长度。
第 2 行, N 个整数, 代表数列中每个数的值。
输出仅一个整数。 如果两人都按照最优策略取, 甲的分数与乙的分数之差。
3 1 2 4
3
对于 30\% 的数据, 1 ≤N ≤1000 .
对于 100\% 的数据, 1 ≤N ≤5 \cdot 10^5,0≤a_i<2^{31} .