Two-Player Optimal Pick Difference

You are given an integer array. Two players take turns picking any one of the remaining elements; both maximize the sum of their own scores, and the first player moves first. Output the first player's total minus the second player's total under optimal play.

输入格式

The first line contains n; the second line contains n integers. Ranges added by this site: 1≤n≤200000, |points[i]|≤10^9.

输出格式

Output score1−score2.

样例 1

输入：

4
4 1 2 3

输出：

2

样例 2

输入：

1
10

输出：

10

样例 3

输入：

3
-5 7 -2

输出：

4