CF1840D Wooden Toy Festival

在一个小镇上，有一家专门从事木工的作坊。由于小镇很小，作坊里只有三位雕刻师。 很快，小镇将举办一次木制玩具节。作坊的员工们希望为此做好准备。 他们知道将会有 $n$ 个人来到作坊，请求制作木制玩具。每个人的需求不同，可能想要不同的玩具。为简单起见，我们用 $a_i$ 表示第 $i$ 个人想要的玩具的样式（$1 \le a_i \le 10^9$）。 每位雕刻师可以提前选择一个整数样式 $x$（$1 \le x \le 10^9$），不同的雕刻师可以选择不同的样式。$x$ 是一个整数。在节日前的准备阶段，雕刻师会完美掌握制作所选样式玩具的技巧，这样他们就能瞬间完成该样式的木制玩具。对于选择了样式 $x$ 的雕刻师来说，制作样式为 $y$ 的玩具需要花费 $|x-y|$ 的时间，因为玩具越接近他能瞬间制作的样式，他完成工作的速度就越快。 在节日当天，每当有顾客来作坊请求制作木制玩具时，雕刻师们可以选择由谁来接单。同时，雕刻师们技艺高超，可以同时为不同顾客工作。 由于人们不喜欢等待，雕刻师们希望选择合适的准备样式，使得所有顾客中的最大等待时间尽可能小。 请输出雕刻师们能够实现的最小的最大等待时间。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示将会有多少人来到作坊。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$（$1 \le a_i \le 10^9$），表示玩具的样式。 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

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

在第一个样例中，雕刻师可以选择准备样式 $1$、$7$、$9$。 在第二个样例中，雕刻师可以选择准备样式 $3$、$30$、$60$。 在第三个样例中，雕刻师可以选择准备样式 $14$、$50$、$85$。 由 ChatGPT 4.1 翻译