CF1840D.Wooden Toy Festival

In a small town, there is a workshop specializing in woodwork. Since the town is small, only three carvers work there.

Soon, a wooden toy festival is planned in the town. The workshop employees want to prepare for it.

They know that $n$ people will come to the workshop with a request to make a wooden toy. People are different and may want different toys. For simplicity, let's denote the pattern of the toy that the $i$-th person wants as $a_i$ ($1 \le a_i \le 10^9$).

Each of the carvers can choose an integer pattern $x$ ($1 \le x \le 10^9$) in advance, different carvers can choose different patterns. $x$ is the integer. During the preparation for the festival, the carvers will perfectly work out the technique of making the toy of the chosen pattern, which will allow them to cut it out of wood instantly. To make a toy of pattern $y$ for a carver who has chosen pattern $x$, it will take $|x - y|$ time, because the more the toy resembles the one he can make instantly, the faster the carver will cope with the work.

On the day of the festival, when the next person comes to the workshop with a request to make a wooden toy, the carvers can choose who will take on the job. At the same time, the carvers are very skilled people and can work on orders for different people simultaneously.

Since people don't like to wait, the carvers want to choose patterns for preparation in such a way that the maximum waiting time over all people is as small as possible.

Output the best maximum waiting time that the carvers can achieve.

在一个小镇上，有一家专精于木工的作坊。由于小镇规模较小，作坊里仅有三名木雕师。

不久后，小镇计划举办一场木制玩具节，作坊员工希望为此做好准备。

他们已知将有 $n$ 位顾客来到作坊，每人提出制作一款木制玩具的需求。每位顾客的需求各不相同，可能想要不同样式的玩具。为简化问题，我们将第 $i$ 位顾客想要的玩具样式记为 $a_i$（其中 $1 \le a_i \le 10^9$）。

每名木雕师可在筹备阶段预先选定一个整数样式 $x$（$1 \le x \le 10^9$），不同木雕师可选择不同的样式。该整数 $x$ 即为其专精样式。在节日前的筹备过程中，每位木雕师将完美掌握其选定样式的制作技巧，从而能瞬间将其从木材中雕刻出来。对于一名已选定样式 $x$ 的木雕师，若需制作样式为 $y$ 的玩具，则所需时间为 $|x - y|$，因为待制玩具与该木雕师专精样式越接近，其完成速度就越快。

节日期间，当一位顾客前来提出制作需求时，木雕师们可自由决定由谁来承接该订单；同时，这些技艺高超的木雕师能够并行处理多位顾客的订单。

由于顾客不愿久等，木雕师们希望预先选定三个样式，使得所有顾客中最大等待时间尽可能小。

请输出木雕师们所能达到的最优（即最小可能的）最大等待时间。

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of a test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of people who will come to the workshop.

The second line of a test case contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($1 \le a_i \le 10^9$) — the patterns of toys.

The sum of all $n$ values over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示将参加工作坊的人数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$（$1 \le a_i \le 10^9$）—— 表示玩具的图案。

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

Output $t$ numbers, each of which is the answer to the corresponding test case — the best maximum waiting time that the carvers can achieve.

输出 $t$ 个数字，每个数字对应一个测试用例的答案——雕刻师们所能达到的最佳最大等待时间。

In the first example, the carvers can choose patterns $1$, $7$, $9$ for preparation.

In the second example, the carvers can choose patterns $3$, $30$, $60$ for preparation.

In the third example, the carvers can choose patterns $14$, $50$, $85$ for preparation.

在第一个例子中，雕刻师可以选择图案 $1$、$7$、$9$ 进行准备。

在第二个例子中，雕刻师可以选择图案 $3$、$30$、$60$ 进行准备。

在第三个例子中，雕刻师可以选择图案 $14$、$50$、$85$ 进行准备。