← 返回题目列表

Codeforces · 1740/C

C. 砖块和袋子

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

有 $$$n$$$ 块,编号从 $$$1$$$ 到 $$$n$$$。砖块 $$$i$$$ 的重量为 $$$a_i$$$。

Pak Chanek 有 $$$3$$$ 行李,编号从 $$$1$$$ 到 $$$3$$$,最初是空的。对于每一块砖,Pak Chanek 必须将其放入其中一个袋子中。此后,每个袋子必须至少包含一块砖块。

Pak Chanek 分发砖块后,Bu Dengklek 将从每个袋子中取出一块砖块。令 $$$w_j$$$ 为 Bu Dengklek 从袋子 $$$j$$$ 中取出的砖块的重量。分数计算公式为 $$$|w_1 - w_2| + |w_2 - w_3|$$$,其中 $$$|x|$$$ 表示 $$$x$$$ 的绝对值。

众所周知,Bu Dengklek 会以最小化分数的方式拿走砖块。如果 Pak Chanek 以最佳方式分配砖块,最终可能获得的最高得分是多少?

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。以下行包含每个测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — 砖块的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 砖块的重量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行,其中包含一个整数,表示如果 Pak Chanek 以最佳方式分配砖块,则表示最大可能的最终分数。

示例

输入 #1

3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265

输出 #1

6
63
0

注意

在第一个测试用例中,获得 $$$6$$$ 最终分数的一种方法是执行以下操作:

- 将砖块 $$$1$$$、$$$4$$$ 和 $$$5$$$ 放入袋子 $$$1$$$ 中。
- 将砖块 $$$3$$$ 放入袋子 $$$2$$$ 中。
- 将砖块 $$$2$$$ 放入袋子 $$$3$$$ 中。

如果 Pak Chanek 以这种方式分配砖块,Bu Dengklek 可以采取的方式是:

- 从袋子 $$$1$$$ 中取出砖块 $$$5$$$。
- 从袋子 $$$2$$$ 中取出砖块 $$$3$$$。
- 从袋子 $$$3$$$ 中取出砖块 $$$2$$$。

得分为 $$$|a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6$$$。可以证明,Bu Dengklek 无法从该分布中得到更小的分数。

可以证明,没有其他分布导致最终得分大于 $$$6$$$。