给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您可以对其执行任意多次(0次或多次)以下操作:
- Choose $$$2$$$ indices $$$i$$$,$$$j$$$ where $$$1 \le i < j \le n$$$ and replace $$$a_k$$$ for all $$$i \leq k \leq j$$$ with $$$|a_i - a_j|$$$
打印通过这种方式可以获得的最终数组的所有元素的最大和。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of array $$$a$$$.
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印最终数组的总和。
示例
输入 #1
3 3 1 1 1 2 9 1 3 4 9 5
输出 #1
3 16 18
注意
In the first test case, it is not possible to achieve a sum $$$> 3$$$ by using these operations, therefore the maximum sum is $$$3$$$.
在第二个测试用例中,可以表明可实现的最大总和为 $$$16$$$。通过使用 $$$(1,2)$$$ 操作,我们将数组从 $$$[9,1]$$$ 转换为 $$$[8,8]$$$,因此最终数组的总和为 $$$16$$$。
In the third test case, it can be shown that it is not possible to achieve a sum $$$> 18$$$ by using these operations, therefore the maximum sum is $$$18$$$.