题目描述

已知一个整形数组arr, 你需要找到满足a<b<c<d的四个数组下标, 使得arr[b]+arr[d]-arr[a]-arr[c]的值最大

输入

第一行输入T,表示测试数据 接下来一行输入n,表示数组长度。（ 4 =< n <= 10^5) 接下来输入n个整数，每个数的范围在[0,10^8] 输出 每组数据输出一行，输出满足条件的最大值

样例输入

1 7 2 3 5 8 1 4 9 样例输出

14

提示

对于测试数据，最大的答案为：

arr[3]+arr[6]-arr[0]-arr[4] = 9 + 8 - 2 - 1 = 14