CF1763C Another Array Problem

给定一个长度为 $n$ 的整数数组 $a$。你可以对其进行如下操作任意多次（可以为 $0$ 次）： - 选择两个下标 $i$、$j$，满足 $1 \le i < j \le n$，然后将所有 $i \leq k \leq j$ 的 $a_k$ 替换为 $|a_i - a_j|$。 请输出通过上述操作后，最终数组所有元素之和的最大值。

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出最终数组元素之和的最大值。

在第一个测试用例中，无法通过操作使数组元素之和大于 $3$，因此最大和为 $3$。 在第二个测试用例中，可以通过操作 $(1,2)$ 将数组 $[9,1]$ 变为 $[8,8]$，此时数组元素之和为 $16$，为最大值。 在第三个测试用例中，无法通过操作使数组元素之和大于 $18$，因此最大和为 $18$。 由 ChatGPT 4.1 翻译