CF1740C.Bricks and Bags

There are $n$ bricks numbered from $1$ to $n$. Brick $i$ has a weight of $a_i$.

Pak Chanek has $3$ bags numbered from $1$ to $3$ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick.

After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $w_j$ be the weight of the brick Bu Dengklek takes from bag $j$. The score is calculated as $|w_1 - w_2| + |w_2 - w_3|$, where $|x|$ denotes the absolute value of $x$.

It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally?

有 $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 以最优方式分配砖块，最终得分的最大可能值是多少？

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the number of bricks.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the weights of the bricks.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a line containing an integer representing the maximum possible final score if Pak Chanek distributes the bricks optimally.

对于每个测试用例，输出一行，包含一个整数，表示如果 Pak Chanek 最优地分配砖块，所能得到的最大最终得分。

In the first test case, one way of achieving a final score of $6$ is to do the following:

• Put bricks $1$, $4$, and $5$ into bag $1$.
• Put brick $3$ into bag $2$.
• Put brick $2$ into bag $3$.

If Pak Chanek distributes the bricks that way, a way Bu Dengklek can take the bricks is:

• Take brick $5$ from bag $1$.
• Take brick $3$ from bag $2$.
• Take brick $2$ from bag $3$.

The score is $|a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6$. It can be shown that Bu Dengklek cannot get a smaller score from this distribution.

It can be shown that there is no other distribution that results in a final score bigger than $6$.

在第一个测试用例中，一种得到最终得分为 $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$ 的最终得分。