给定一个数组 $$$a$$$,其中包含 $$$n$$$ 整数。您可以选择此数组的任何合适的子段 $$$a_l, a_{l + 1}, \ldots, a_r$$$,这意味着您可以选择任意两个整数 $$$1 \le l \le r \le n$$$,其中 $$$r - l + 1 < n$$$。我们将给定子段的美感定义为以下表达式的值:
$$$$$$\max(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) - \min(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) + \max(a_{l}, \ldots, a_{r}) - \min(a_{l}, \ldots, a_{r}).$$$$$$
请在所有适当的子段中找到最大的美。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。然后遵循每个测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(4 \leq n \leq 10^5)$$$ — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_{i} \leq 10^9$$$) — 给定数组的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
为每个测试用例打印一个整数——适当子段的最大美感。
示例
输入 #1
4 8 1 2 2 3 1 5 6 1 5 1 2 3 100 200 4 3 3 3 3 6 7 8 3 1 1 8
输出 #1
9 297 0 14
注意
在第一个测试用例中,最佳段是 $$$l = 7$$$,$$$r = 8$$$。该段的美丽程度等于 $$$(6 - 1) + (5 - 1) = 9$$$。
在第二个测试用例中,最佳段是 $$$l = 2$$$,$$$r = 4$$$。该段的美丽值等于 $$$(100 - 2) + (200 - 1) = 297$$$。