该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为$x$ 和$y$，且 $x \leqslant y$。那么粉碎的可能结果如下：

• 如果$x == y$，那么两块石头都会被完全粉碎；
• 如果 $x != y$，那么重量为$x$的石头将会完全粉碎，而重量为 $y$ 的石头新重量为$y-x$。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

输入格式

第一行，一个整数，石头的数量$n$

第二行，$n$个石头重量，空格分开

输出格式

输出剩下石头的重量，如果没有石头剩下，就返回 0

样例

6
2 7 4 1 8 1

1

样例解释:

先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]

再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]

接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]

最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

数据范围

$1 \leqslant n \leqslant 30$

$1 \leqslant$ 石头重量 $\leqslant 1000$

来源

LeetCode 1046