You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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}$.