Snowdrop的玩偶7
Problem Description
Author: eedwang
Snowdrop 有很多隻 Gura 玩偶，每一隻都有一個價格。
已知 Snowdrop 總共有 n 隻玩偶，且 n 一定是偶數。現在 Snowdrop 想要把這些玩偶分成 n/2 對。 每隻玩偶只能被使用一次，不能同時出現在兩個不同的配對中。
對於一對玩偶 (x,y)，它們的「差值」定義為 |x - y|。 Snowdrop 想要把玩偶們分成配對，使得所有配對的「差值」中最大的那個，盡可能小。
請你幫 Snowdrop 求出：這個「最大差值」的最小可能值。
Input Format
第一行包含一個整數 t (1 ≤ t ≤ 103)，代表測資組數。 接下來每組測資包含兩行：
- 第一行輸入一個偶數 n (2 ≤ n ≤ 2⋅105)，代表 Snowdrop 擁有的玩偶數量。
- 第二行輸入 n 個整數 a1,a2,…,an (−103 ≤ ai ≤ 103)，代表每隻玩偶的價格。
Output Format
對於每組測資，輸出一個整數，代表能達到的最小「最大差值」。
6
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
8
1 1 1 1 1 1 9 9
1
1
1
0
4
0
Hint
記得在main裡面第一行加上ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);