在一个小镇上,有一家专门从事木工的作坊。由于小镇很小,只有三个雕刻师在那里工作。
很快,镇上计划举办木制玩具节。车间员工要做好准备。
他们知道会有 $$$n$$$ 人来到工作室要求制作木制玩具。人们是不同的,可能想要不同的玩具。为简单起见,我们将第 $$$i$$$ 人想要的玩具图案表示为 $$$a_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 \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$$$数字,每个数字都是相应测试用例的答案——雕刻师可以达到的最佳最大等待时间。
示例
输入 #1
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
输出 #1
0 2 13 0 1
注意
在第一个示例中,雕刻师可以选择图案 $$$1$$$、$$$7$$$、$$$9$$$ 进行准备。
在第二个例子中,雕刻师可以选择图案 $$$3$$$、$$$30$$$、$$$60$$$ 进行准备。
在第三个例子中,雕刻师可以选择图案$$$14$$$、$$$50$$$、$$$85$$$进行准备。