Bricks and Bags
Contest: Codeforces Round 831 (Div. 1 + Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, games, greedy, sortings

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?

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265

Example output:
6
63
0

Editorial:
Firstly, sort $$$a$$$. From now on, we will always refer to the sorted array $$$a$$$.
Let $$$p_j$$$ be the index of the brick taken by Bu Dengklek from bag $$$j$$$. The configuration of $$$p_1,p_2,p_3$$$ must be in the form of one of the following:
1. $$$p_1 < p_2 < p_3$$$
2. $$$p_1 > p_2 > p_3$$$
3. $$$p_2 < \min(p_1, p_3)$$$
4. $$$p_2 > \max(p_1, p_3)$$$
Let's look at the third case. Let's consider the case where $$$\min(p_1, p_3) > p_2+1$$$. If this is the case, let's look at all possible cases for the brick at index $$$p_2+1$$$.
• If Pak Chanek puts brick $$$p_2+1$$$ into bag $$$1$$$, it is more optimal for Bu Dengklek to take that brick from bag $$$1$$$ instead of $$$p_1$$$ because $$$a_{p_2+1}-a_{p_2} \leq a_{p_1}-a_{p_2}$$$.
• If Pak Chanek puts brick $$$p_2+1$$$ into bag $$$2$$$, it is more optimal for Bu Dengklek to take that brick from bag $$$2$$$ instead of $$$p_2$$$ because $$$(a_{p_1}-a_{p_2+1})+(a_{p_3}-a_{p_2+1}) \leq (a_{p_1}-a_{p_2})+(a_{p_3}-a_{p_2})$$$.
• If Pak Chanek puts brick $$$p_2+1$$$ into bag $$$3$$$, it is more optimal for Bu Dengklek to take that brick from bag $$$3$$$ instead of $$$p_3$$$ because $$$a_{p_2+1}-a_{p_2} \leq a_{p_3}-a_{p_2}$$$.
This means, choosing $$$p_1,p_2,p_3$$$ such that $$$\min(p_1, p_3) > p_2+1$$$ is always less optimal for Bu Dengklek. Therefore, Bu Dengklek will take the bricks such that if $$$p_2 < \min(p_1, p_3)$$$, then $$$\min(p_1, p_3) = p_2 + 1$$$ also holds.
A similar logic can be used for the fourth case. So, we can obtain that Bu Dengklek will always take the bricks such that the configuration of $$$p_1,p_2,p_3$$$ is in the form of one of the following:
1. $$$p_1 < p_2 < p_3$$$
2. $$$p_1 > p_2 > p_3$$$
3. $$$p_2 < \min(p_1, p_3)$$$ and $$$\min(p_1, p_3) = p_2 + 1$$$
4. $$$p_2 > \max(p_1, p_3)$$$ and $$$\max(p_1, p_3) = p_2 - 1$$$
In fact, Pak Chanek is always able to force it such that the bricks taken by Bu Dengklek form any configuration of $$$p_1,p_2,p_3$$$ that follows one of the constraints above. Let's look at one possible construction. For a configuration of $$$p_1,p_2,p_3$$$ construct an order of the bags $$$j_1,j_2,j_3$$$ such that $$$p_{j_1}<p_{j_2}<p_{j_3}$$$. Then, Pak Chanek can force Bu Dengklek to choose that configuration by doing the following:
• Put the bricks at indices from $$$1$$$ to $$$p_{j_1}$$$ into bag $$$j_1$$$.
• Put the bricks at indices from $$$p_{j_1}+1$$$ to $$$p_{j_3}-1$$$ into bag $$$j_2$$$.
• Put the bricks at indices from $$$p_{j_3}$$$ to $$$n$$$ into bag $$$j_3$$$.
Therefore, we just need to find the values of $$$p_1,p_2,p_3$$$ satisfying the constraints above such that $$$|a_{p_1}-a_{p_2}|+|a_{p_2}-a_{p_3}|$$$ is maximised.
To maximise the final score, we can see that it is always more optimal to either use the third or the fourth case for $$$p_1,p_2,p_3$$$. For the third case, it is always more optimal to maximise $$$\max(p_1, p_3)$$$, so we should set $$$\max(p_1, p_3) = n$$$. A similar logic can be used for the fourth case to see that we should set $$$\min(p_1, p_3) = 1$$$.
Therefore, the maximum final score is the maximum of these two cases:
• $$$(a_i-a_{i-1})+(a_i-a_1)$$$ with $$$3 \leq i \leq n$$$.
• $$$(a_{i+1}-a_i)+(a_n-a_i)$$$ with $$$1 \leq i \leq n-2$$$.
Time complexity for each test case: $$$O(n \log n)$$$