CF1740C Bricks and Bags

有 $n$ 块砖头，编号从 $1$ 到 $n$。第 $i$ 块砖头的重量为 $a_i$。 Pak Chanek 有 $3$ 个编号为 $1$ 到 $3$ 的袋子，初始时都是空的。对于每一块砖头，Pak Chanek 必须将其放入其中一个袋子。分配完后，每个袋子中至少要有一块砖头。 Pak Chanek 分配完砖头后，Bu Dengklek 会从每个袋子中各取出一块砖头。设 Bu Dengklek 从第 $j$ 个袋子中取出的砖头重量为 $w_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 以最优方式分配砖头，最终得分的最大可能值。

在第一个测试点中，一种能获得最终得分 $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$。 由 ChatGPT 4.1 翻译