Description

译自 POI 2010 Stage 3. Day 1「The Minima Game」

Alice 和 Bob 玩一个游戏。Alice 先手，两人轮流进行操作，每轮一个玩家可以选择若干张牌（至少一张），并获得相当于这些牌上所写数字的最小值的分数，直到没有牌为止。两人都希望自己的分数与对方分数之差最大。若两个玩家都使用最佳策略，求游戏的最终结果。

Input Format

第一行有一个整数 $n$，表示牌的数量。

接下来一行有 $n$ 个正整数 $k_1, k_2, ..., k_n$，表示牌上所写的数字。

Output Format

输出一行一个整数，表示最终 Alice 的分数与 Bob 分数之差。如果 Bob 的分数更多，你应该输出一个负数。

样例解释

Alice 先选择 $3$，得到 $3$ 分。Bob 拿走所有牌并得到 $1$ 分，游戏最后的比分为 $3:1$，因此 Alice 比 Bob 多两分。

3
1 3 1

2

Hint

$1\le n\le 10^6$，$1\le k_i\le 10^9$。

翻译来自于 LibreOJ。