题目描述

一档名为 Unconventional Pairs 的热门真人秀在城市里开播了。根据节目规则，参与者的配对方式非常独特：如果总人数是偶数，则所有参与者都必须两两配对。

Petya 有一个长度为 $n$ 的整数数组 $a_1,a_2,\dots ,a_n$。已知 $n$ 是偶数。Petya 需要将这些“参与者”（数字）恰好分成 $\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$。

由 ChatGPT 5 翻译

来源

Codeforces 2149B，英文题名 Unconventional Pairs。