小 A 和小 B 又在通过游戏决一胜负了。

今天他们玩的游戏是这样的：小 A 拿出了 n 张卡片，每张卡片上都写了一个数 a_i。他们每个人轮流交替取走一张卡片，直到取完，小 A 先取。

记小 A 取走的卡片的权值和为 A，小 B 取走的卡片的权值和为 B，则小 A 最终得分为 |A| - |B|。小 A 自然希望自己的得分最大，小 B 则希望其得分最小。

他们想知道在他们都采取最优策略的情况下，小 A 的最终得分是多少。

第一行包含一个整数 n。

第二行包含 n 个整数 a_1, a_2, \ldots, a_n，表示小 A 拿出的 n 张卡片。

输出一行一个整数，表示小 A 的最终得分。

样例 1 解释

小 A 先取 -6，小 B 取 -3；小 A 取 -1，小 B 取 -1；小 A 取 4，小 B 取 6。

小 A 的和为 -6-1+4 = -3，小 B 的和为 -3-1+6 = 2，最终得分 |-3| - |2| = 1。

数据范围

对于 100\% 的数据，1 \le n \le 10^5,\ |a_i| \le 10^9。

• 1 \sim 2：n = 2；
• 3 \sim 4：n = 4；
• 5 \sim 6：n = 6；
• 7 \sim 8：n \le 10^3；
• 9 \sim 12：a_i > 0；
• 13 \sim 16：a_i < 0；
• 17 \sim 20：无特殊性质。

提示

如果所有卡片的和为负，把所有卡片取相反数，答案不变——这样两人的和都变成了非负，「谁的绝对值大」就等价于「谁拿的数大」。

于是把卡片从大到小排序，两个人轮流取：先手拿第 1, 3, 5, \ldots 张，后手拿第 2, 4, 6, \ldots 张，这就是双方的最优策略，时间复杂度 O(n \log n)。