Description

给出一个数列 a, 甲乙两人每次从数列中拿取一个数，直到取完为止。 甲先手。获得的分数为每人取到所有数字的数字和。

现在藤藤想知道， 如果两人都按照最优策略取， 甲的分数比乙高多少。

Format

Input

输入共 $2$ 行。

第 $1$ 行， 一个整数 $N$ , 代表数列 $a$ 的长度。

第 $2$ 行， $N$ 个整数， 代表数列中每个数的值。

Output

输出仅一个整数。 如果两人都按照最优策略取， 甲的分数与乙的分数之差。

Samples

3
1 2 4

3

Limitation

1s, 1024KiB for each test case.

对于 $30\%$ 的数据， $1 ≤N ≤1000$.

对于 $100\%$ 的数据， $1 ≤N ≤5 \cdot 10^5,0≤a_i<2^{31}$.