4462: 「POI2010」最小化游戏 The Minima Game
内存限制：32 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**译自 POI 2010 Stage 3. Day 1「[The Minima Game](https://szkopul.edu.pl/problemset/problem/3buviDQZWLE83AxVhvJJurgU/site/?key=statement)」**
Alice 和 Bob 玩一个游戏。Alice 先手，两人轮流进行操作，每轮一个玩家可以选择若干张牌（至少一张），并获得相当于这些牌上所写数字的最小值的分数，直到没有牌为止。两人都希望自己的分数与对方分数之差最大。若两个玩家都使用最佳策略，求游戏的最终结果。
输入
第一行有一个整数 $n$，表示牌的数量。
接下来一行有 $n$ 个正整数 $k_1, k_2, ..., k_n$，表示牌上所写的数字。
输出
输出一行一个整数，表示最终 Alice 的分数与 Bob 分数之差。如果 Bob 的分数更多，你应该输出一个负数。
样例输入 复制
3
1 3 1样例输出 复制
2提示
数据范围：对于 $100\%$ 的数据， $1 \le n \le 1000000 , 1 \le k_i \le 10^9$ 。 Translated by vincent163