310479: CF1840D. Wooden Toy Festival

D. Wooden Toy Festivaltime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExampleInput

5
6
1 7 7 9 9 9
6
5 4 2 1 30 60
9
14 19 37 59 1 4 4 98 73
1
2
6
3 10 1 17 15 11

Output

0
2
13
0
1

Note

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.

题目大意：
小镇上的木工坊将举办木制玩具节。有三位雕刻师，每个人可以提前选择一个玩具图案\(x\)（\(1 \le x \le 10^9\)），不同雕刻师可以选择不同的图案。如果雕刻师选择了图案\(x\)，那么对于任何图案\(y\)，制作这个玩具需要的时间是\(|x - y|\)。在节日当天，当有人要求制作玩具时，雕刻师可以选择谁来制作，且他们可以同时为不同的人工作。目标是使得所有人中最大的等待时间尽可能小。输入是一系列测试用例，每个测试用例包含人数\(n\)和每个人想要的玩具图案，输出是每个测试用例的最佳最大等待时间。

输入输出数据格式：
输入：
- 第一行包含一个整数\(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\)。

输出：
- 输出\(t\)个整数，每个数对应一个测试用例的最佳最大等待时间。题目大意： 小镇上的木工坊将举办木制玩具节。有三位雕刻师，每个人可以提前选择一个玩具图案\(x\)（\(1 \le x \le 10^9\)），不同雕刻师可以选择不同的图案。如果雕刻师选择了图案\(x\)，那么对于任何图案\(y\)，制作这个玩具需要的时间是\(|x - y|\)。在节日当天，当有人要求制作玩具时，雕刻师可以选择谁来制作，且他们可以同时为不同的人工作。目标是使得所有人中最大的等待时间尽可能小。输入是一系列测试用例，每个测试用例包含人数\(n\)和每个人想要的玩具图案，输出是每个测试用例的最佳最大等待时间。 输入输出数据格式： 输入： - 第一行包含一个整数\(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\)。 输出： - 输出\(t\)个整数，每个数对应一个测试用例的最佳最大等待时间。