作为格斗场管理者的你现有n位格斗士，依次编号为1,2,…,n，第i位格斗士的等级为ai。
你将安排n-1场格斗比赛，每场比赛你将会从未淘汰的格斗士当中选出两位格斗士进行格斗比赛，假定你选择第i位格斗士和第j位格斗士（1<=i<j<=n）进行比赛，比赛结果一定是第i位格斗士被淘汰，第j位格斗士会获胜，但他的等级会下降ai（因为他经过一场激烈的比赛后受伤了），即aj=aj-ai.请注意，格斗士的等级可以为负数。所有格斗士的编号不会发生改变。
请问，你如何安排比赛使得剩下的最后一位格斗士的等级最高？
作为格斗场管理者的你现有n位格斗士，依次编号为1,2,…,n，第i位格斗士的等级为ai。
你将安排n-1场格斗比赛，每场比赛你将会从未淘汰的格斗士当中选出两位格斗士进行格斗比赛，假定你选择第i位格斗士和第j位格斗士（1<=i<j<=n）进行比赛，比赛结果一定是第i位格斗士被淘汰，第j位格斗士会获胜，但他的等级会下降ai（因为他经过一场激烈的比赛后受伤了），即aj=aj-ai.请注意，格斗士的等级可以为负数。所有格斗士的编号不会发生改变。
请问，你如何安排比赛使得剩下的最后一位格斗士的等级最高？
第一行一个整数t（1≤t≤1e4）：测试样例数；
每个测试样例2行：
第一行一个整数n（2≤n≤2e5）：格斗士的数量；
第二行共n个整数a1,a2,…,an(1≤ai≤1e9)：ai为第i位格斗士的等级；
测试数据确保，所有测试样例的n之和不超过2e5.
输出共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和2的两位格斗士进行比赛，即i=1，j=2，第1位格斗士被淘汰，第2位格斗士获胜，等级为：a2-a1=1-2=-1;
对于第2个测试样例，你可以这样安排：第1场比赛安排编号为1和2的两位格斗士进行比赛，即i=1，j=2，第1位格斗士被淘汰，第2位格斗士获胜，等级为：a2-a1=2-2=0;第2场比赛安排编号为2和3的两位格斗士进行比赛，即i=2，j=3，第2位格斗士被淘汰，第3位格斗士获胜，等级为：a3-a2=8-0=8.因此，最后的格斗士的等级为8.显然，这已经是最大了。