Alice 和 Bob 最近学会了“最小值游戏”，他们非常喜欢这个游戏。游戏规则如下：桌上放着若干张卡片，每张卡片上写有一个正整数。玩家轮流进行操作，Alice 先手。每次操作，玩家可以从桌上任意选取一张或多张卡片。该次操作玩家获得的得分为所选卡片上数字的最小值。当桌上最后一张卡片被取走时，游戏结束。每位玩家的目标是最大化自己与对手的得分差。

Alice 和 Bob 已经注意到这个游戏存在最优策略。因此，他们请求你编写一个程序，对于给定的卡片集合，计算当双方都采取最优策略时，游戏的结果。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示卡片的数量。第二行包含 $n$ 个正整数 $k_1, k_2, \dots, k_n$ ($1 \le k_i \le 10^9$)，由空格分隔，表示卡片上的数字。

输出格式

输出一行，包含一个整数，表示在双方均采取最优策略的情况下，Alice 比 Bob 多出的分数；如果 Bob 的分数更高，则结果应为负数。

样例

输入 1

3
1 3 1

输出 1

2

说明 1

Alice 选取一张卡片，即写有 3 的那张，这使她获得 3 分。Bob 取走剩余的两张卡片，获得 1 分。游戏以 3 比 1 的比分结束，因此 Alice 赢了 2 分。