Get Score Difference

Two players take turns picking any positive integer from the remaining array, adding it to their own score and removing it. Player 1 moves first, and play continues until the array is empty. Both players want to maximize their own final score; find the absolute difference between the two scores under optimal play.

输入格式

The first line contains n (1..100000), and the second line contains n values (1..10⁹).

输出格式

Output a single integer, the answer required by the problem.

样例 1

输入：

4
4 1 2 3

输出：

2

样例 2

输入：

1
9

输出：

9

样例 3

输入：

3
1 1 1

输出：

1

样例说明

In example 1, 4, 3, 2, 1 are taken in order; player 1 gets 6 and player 2 gets 4, so the difference is 2.