题目描述

源老师的班里管理着 $n$ 位同学，第 $i$ 位同学的战斗力是 $a_i$

他安排了 $n-1$ 场淘汰赛。在每次比赛中，你要选择 两名未被淘汰的同学 $i$ 和 $j$。（必须保证 $1\leq i<j\leq n$）。

这场战斗比较特殊，编号小的人一定被淘汰，编号大的人战斗力会损失一部分。也就是说编号 $i$ 的人被淘汰，编号 $j$ 的人的战斗力变更为 $a_j-a_i$。战斗力也可以变为负数。

源老师想知道，如何安排战斗，使得最后剩下的人的战斗力最高。

输入格式

本题有多组测试数据，第一行输入一个整数 $t$

接下来 $t$ 组数据，每组数据的第一行首先输入一个整数 $n$

接下来一行输入 $n$ 个空格隔开的整数 $a_1,a_2,\cdots,a_n$

输出格式

一共输出 $t$ 行，输出一个整数代表答案。

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

样例 1 解释

• 第一组数据中，只能淘汰 $1$，$a_2-a_1=-1$，这是最后的人员战斗力。
• 第二组数据中，先让 $1,2$ 战斗淘汰 $1$，此时 $a_2=2-2=0$，再让 $2,3$ 战斗淘汰 $2$，此时 $a_3=8-0=8$。因此最后输出 $8$

数据范围

• $20\%$ 的数据满足，$1\leq t\leq 10$，$n=2$，$1\leq a_i\leq 10^2$
• $40\%$ 的数据满足，$1\leq t\leq 10$，$n=3$，$1\leq a_i\leq 10^2$
• $50\%$ 的数据满足，$1\leq t\leq 10$，$n=4$，$1\leq a_i\leq 10^2$
• $100\%$ 的数据满足，$1\leq t\leq 10^4$，$2\leq n\leq 10^5$，$1\leq a_i\leq 10^9$

保证每一组的数据的 $n$ 的和不超过 $2\times 10^5$

即 $\sum\limits_{i=1}^t n\leq 2\times 10^5$