Problem C: PIPI的数学题V

Problem C: PIPI的数学题V

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 248  Solved: 83
[Submit] [Status] [Web Board] [Creator:]

Description

大家知道欧几里得距离,曼哈顿距离等,PIPI今天心血来潮,定义了一个PIPI距离, 使用这种距离,PIPI可以准确的估计两个元素的匹配度。

 

现在PIPI想在一堆元素中找到匹配度最大的两个元素,PIPI不关心这两个元素是啥,他只想知道他们的最大匹配度是多少,你能告诉PIPI吗?

Input

第一行输入一个正整数T(T<=10),代表测试样例组数。
对于每组样例,输入一个正整数n (n<=1e5)代表元素的个数。
接下来输入n个整数Ai (-1e9<=Ai<=1e9),代表元素的值。

Output

输出T个整数,代表最大匹配度。

Sample Input

2
2
4 3
4
5 4 -9 2

Sample Output

10
84