12501: 最强战士

Eralim 是老大，管理着一群战士。战士 $i$ 的等级为 $a_i$ 。 Eralim安排了一场由 $n - 1$ 场战斗组成的锦标赛，在每场战斗中选出两名尚未被淘汰的战士 $i$ 和 $j$ ，战斗的结果是战士 $i$ 被淘汰出锦标赛，战士 $j$ 的等级被战士 $i$ 的等级所降低。也就是说， $a_j$ 减少了 $a_i$ 。请注意，战士 $j$ 的等级可以变为负数。战士的指数不会改变（$1 \le i < j \le n$）。 Eralim想知道，如果他最优化地选择战斗，最后剩下的战士能保持的最高等级是多少。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ 。测试用例说明如下。 每个测试用例的第一行都包含一个整数 $n$ 战士的数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots a_n$ 战士的评分。

对于每个测试案例，输出一个整数，即最后剩下的战士所能保留的最大等级。

5
2
2 1
3
2 2 8
4
1 2 4 3
5
1 2 3 4 5
5
3 2 4 5 4

-1
8
2
7
8