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$$$。