CF2149B Unconventional Pairs

A popular reality show Unconventional Pairs has been launched in the city. According to the rules of the show, participants are paired in an unusual way: with an even number of people, all participants must be in pairs. Petya has an array of $ n $ integers $ a_1,a_2,\dots ,a_n $ . It is known that $ n $ is even. Petya must divide the participants (numbers) into exactly $ \large\frac{n}{2} $ pairs $ (a_{p_1},a_{q_1}),\,(a_{p_2},a_{q_2}),\dots\,(a_{p_\frac{n}{2}},a_{q_\frac{n}{2}}) $ . Each index can be included in no more than one pair. For a pair $ (x,y) $ , its difference is defined as $ |x-y| $ . Petya wants to form unconventional pairs such that the maximum difference among all pairs is minimized. Determine the minimum possible value of this maximum difference.

Each test consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains one even number $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1,a_2,\dots ,a_n $ $ (-10^{9} \le a_i \le 10^{9}) $ — the elements of the array $ a $ . It is guaranteed that the sum of the values of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single number — the minimum possible maximum difference between the elements in pairs.

In the first test case, the array is: $ [1,2] $ . The only possible (and therefore optimal) pair is $ (1,2) $ , its difference is $ |1-2| = 1 $ , the answer is $ 1 $ . In the second test case, the array is: $ [10,1,2,9] $ . We can choose pairs — $ (1,2) $ and $ (9,10) $ : both differences are equal to $ 1 $ , therefore, the maximum difference is $ 1 $ . In the third test case, the array is: $ [3,8,9,3,3,2] $ . We can choose pairs: $ (2,3) $ , $ (3,3) $ , $ (8,9) $ . The differences are: $ 1,0,1 $ — the largest is $ 1 $ .