[AdditionalFile2455.zip](file://AdditionalFile2455.zip?type=additional_file)

#2455. 「POI2010」最小化游戏 The Minima Game

标签: 传统 | 时间限制: 1000 ms | 内存限制: 32 MiB |

题目描述

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

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

输入格式

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

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

输出格式

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

样例

输入

3
1 3 1

输出

2

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

数据范围与提示

对于 $100\%$ 的数据， $1 \le n \le 1000000 , 1 \le k_i \le 10^9$ 。

Translated by vincent163