← 返回题目列表

Codeforces · 2013/B

B. 生存之战

中文机器翻译题面 查看原题

Eralim,作为黑手党老大,管理着一群$$$n$$$战士。战斗机 $$$i$$$ 的评级为 $$$a_i$$$。

Eralim 安排了一场 $$$n - 1$$$ 战斗的锦标赛,每场比赛选择两名尚未淘汰的战士 $$$i$$$ 和 $$$j$$$ ($$$1 \le i < j \le n$$$),战斗结果是,战士 $$$i$$$ 从锦标赛中被淘汰,战士 $$$j$$$ 的评级会减少战斗机$$$i$$$。也就是说,$$$a_j$$$ 减少了$$$a_i$$$。请注意,战斗机 $$$j$$$ 的评级可能会变为负值。战士指数没有变化。

Eralim 想知道如果他选择最佳的战斗,最后剩下的战士可以保留多少最大等级。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 战士的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 战士的评级。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 最后剩下的战斗机可以保留的最大评级。

示例

输入 #1

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

-1
8
2
7
8

注意

在第一个示例中,您可以安排索引为 $$$1$$$ 和 $$$2$$$ 的战士之间的战斗,索引为 $$$2$$$ 的战士将获胜。最后一个战斗机,即索引为$$$2$$$的战斗机的评级将为$$$1 - 2 = -1$$$。

在第二个例子中,您可以先在索引为 $$$1$$$ 和 $$$2$$$ 的战士之间进行战斗,其中索引为 $$$2$$$ 的战士获胜,然后在索引为 $$$2$$$ 和 $$$3$$$ 的战士之间进行战斗,其中索引为 $$$3$$$ 的战士获胜。

指数为$$$2$$$的战士在第一次战斗后的评分将为$$$2 - 2 = 0$$$。第二场比赛后索引为$$$3$$$的战斗机的评级将为$$$8 - 0 = 8$$$。