← 返回题目列表

Codeforces · 1763/C

C. 另一个数组问题

中文机器翻译题面 查看原题

给定一个由 $$$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$$$.