← 返回题目列表

Codeforces · 2149/B

B. 非常规配对

中文机器翻译题面 查看原题

热门真人秀节目 非常规对 已在全市推出。根据演出规则,参与者以一种不寻常的方式配对:人数为偶数时,所有参与者都必须成双成对。

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

输出

对于每个测试用例,输出一个数字 - 成对元素之间的最小可能最大差异。

示例

输入
复制

5
2
1 2
4
10 1 2 9
6
3 8 9 3 3 2
8
5 5 5 5 5 5 5 5
4
-5 -1 2 6

输出
复制

1
1
1
0
4

注意

在第一个测试用例中,数组为:$$$[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$$$。