热门真人秀节目 非常规对 已在全市推出。根据演出规则,参与者以一种不寻常的方式配对:人数为偶数时,所有参与者都必须成双成对。
Petya 有一个 $$$n$$$ 整数 $$$a_1,a_2,\dots ,a_n$$$ 数组。已知 $$$n$$$ 是偶数。 Petya 必须将参与者(数字)准确地分成 $$$\large\frac{n}{2}$$$ 对 $$$(a_{p_1},a_{q_1}),\,(a_{p_2},a_{q_2}),\dots\,(a_{p_\frac{n}{2}},a_{q_\frac{n}{2}})$$$。每个索引最多可以包含在一对中。
对于一对$$$(x,y)$$$,其 区别 定义为 $$$|x-y|$$$。 Petya想要组建 非常规对 这样 最大 所有对之间的差异被最小化。
确定该最大差值的最小可能值。
输入
每个测试由多个测试用例组成。
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个偶数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\dots ,a_n$$$ $$$(-10^{9} \le a_i \le 10^{9})$$$ — 数组 $$$a$$$ 的元素。
保证所有测试用例中 $$$n$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个数字 - 成对元素之间的最小可能最大差异。
示例
输入复制
521 2410 1 2 963 8 9 3 3 285 5 5 5 5 5 5 54-5 -1 2 6
输出复制
11104
注意
在第一个测试用例中,数组为:$$$[1,2]$$$。唯一可能的(因此也是最佳的)对是 $$$(1,2)$$$,其差异是 $$$|1-2| = 1$$$,答案是$$$1$$$。
在第二个测试用例中,数组为:$$$[10,1,2,9]$$$。我们可以选择对 - $$$(1,2)$$$ 和 $$$(9,10)$$$:两个差值都等于 $$$1$$$,因此,最大差值是 $$$1$$$。
在第三个测试用例中,数组为:$$$[3,8,9,3,3,2]$$$。我们可以选择对:$$$(2,3)$$$、$$$(3,3)$$$、$$$(8,9)$$$。差异是:$$$1,0,1$$$ — 最大的是 $$$1$$$。