在探索丛林时,您遇到了一只罕见的打着领结的猩猩!你与猩猩握手并给他一些食物和水。作为回报...
猩猩送给你一个长度为 $$$n$$$ 的数组 $$$a$$$。使用 $$$a$$$,您将按照以下方式构造两个数组 $$$b$$$ 和 $$$c$$$,它们都包含 $$$n$$$ 元素:
- $$$b_i = \min(a_1, a_2, \ldots, a_i)$$$ 对于每个 $$$1 \leq i \leq n$$$。
- $$$c_i = \max(a_1, a_2, \ldots, a_i)$$$ 对于每个 $$$1 \leq i \leq n$$$。
将 $$$a$$$ 的分数定义为 $$$\sum_{i=1}^n c_i - b_i$$$ (即 $$$c_i - b_i$$$ 对所有 $$$1 \leq i \leq n$$$ 的总和)。在计算分数之前,您可以根据需要随意打乱 $$$a$$$ 的元素。
找出以最佳方式对 $$$a$$$ 的元素进行洗牌后可以获得的最高分数。
输入
第一行包含 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$) — $$$a$$$ 中的元素数量。
以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,输出您可以获得的最高分数。
示例
输入 #1
3 1 69 3 7 6 5 5 1 1 1 2 2
输出 #1
0 4 4
注意
在第一个测试用例中,没有其他方法可以重新排列$$$a$$$。因此,$$$b = [69]$$$ 和 $$$c = [69]$$$。唯一可能的分数是 $$$69 - 69 = 0$$$。
在第二个测试用例中,您可以将 $$$a$$$ 重新排列为 $$$[7, 5, 6]$$$。这里,$$$b = [7, 5, 5]$$$ 和 $$$c = [7, 7, 7]$$$。本例中的分数为 $$$(7 - 7) + (7 - 5) + (7 - 5) = 4$$$。可以证明这是最大可能的分数。