CF1300B.Assigning to Classes

Reminder: the median of the array $[a_1, a_2, \dots, a_{2k+1}]$ of odd number of elements is defined as follows: let $[b_1, b_2, \dots, b_{2k+1}]$ be the elements of the array in the sorted order. Then median of this array is equal to $b_{k+1}$.

There are $2n$ students, the $i$-th student has skill level $a_i$. It's not guaranteed that all skill levels are distinct.

Let's define skill level of a class as the median of skill levels of students of the class.

As a principal of the school, you would like to assign each student to one of the $2$ classes such that each class has odd number of students (not divisible by $2$). The number of students in the classes may be equal or different, by your choice. Every student has to be assigned to exactly one class. Among such partitions, you want to choose one in which the absolute difference between skill levels of the classes is minimized.

What is the minimum possible absolute difference you can achieve?

提示：对于含有奇数个元素的数组 $[a_1, a_2, \dots, a_{2k+1}]$，其中位数（median）定义如下：设 $[b_1, b_2, \dots, b_{2k+1}]$ 为该数组按升序排列后的元素序列，则该数组的中位数即为 $b_{k+1}$。

共有 $2n$ 名学生，第 $i$ 名学生的技能水平为 $a_i$。注意：这些技能水平不一定互不相同。

我们定义一个班级的技能水平为该班级所有学生技能水平的中位数。

作为该校校长，您希望将每名学生恰好分配到两个班级中的一个，使得每个班级的学生人数均为奇数（即不能被 $2$ 整除）。两个班级的学生人数可以相等，也可以不同，由您自行决定。每名学生必须且只能被分配到一个班级。在所有满足上述条件的分配方案中，您希望选择一种使得两个班级技能水平之差的绝对值最小的方案。

您所能达到的最小可能的绝对差值是多少？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of students halved.

The second line of each test case contains $2n$ integers $a_1, a_2, \dots, a_{2 n}$ ($1 \le a_i \le 10^9$) — skill levels of students.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 表示学生人数的一半。

每个测试用例的第二行包含 $2n$ 个整数 $a_1, a_2, \dots, a_{2 n}$（$1 \le a_i \le 10^9$）—— 表示学生的技能水平。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, output a single integer, the minimum possible absolute difference between skill levels of two classes of odd sizes.

对于每个测试用例，输出一个整数，即两个奇数大小班级之间技能水平的最小可能绝对差值。

In the first test, there is only one way to partition students — one in each class. The absolute difference of the skill levels will be $|1 - 1| = 0$.

In the second test, one of the possible partitions is to make the first class of students with skill levels $[6, 4, 2]$, so that the skill level of the first class will be $4$, and second with $[5, 1, 3]$, so that the skill level of the second class will be $3$. Absolute difference will be $|4 - 3| = 1$.

Note that you can't assign like $[2, 3]$, $[6, 5, 4, 1]$ or $[]$, $[6, 5, 4, 1, 2, 3]$ because classes have even number of students.

$[2]$, $[1, 3, 4]$ is also not possible because students with skills $5$ and $6$ aren't assigned to a class.

In the third test you can assign the students in the following way: $[3, 4, 13, 13, 20], [2, 5, 8, 16, 17]$ or $[3, 8, 17], [2, 4, 5, 13, 13, 16, 20]$. Both divisions give minimal possible absolute difference.

在第一个测试用例中，只有一种分班方式——每班各一人。技能水平的绝对差值为 $|1 - 1| = 0$。

在第二个测试用例中，一种可行的分班方案是：将技能水平为 $[6, 4, 2]$ 的学生分入第一班，则第一班的技能水平为 $4$；将技能水平为 $[5, 1, 3]$ 的学生分入第二班，则第二班的技能水平为 $3$。此时绝对差值为 $|4 - 3| = 1$。

注意，你不能采用 $[2, 3]$, $[6, 5, 4, 1]$ 或 $[]$, $[6, 5, 4, 1, 2, 3]$ 这样的分配方式，因为每班的学生人数必须为偶数。

$[2]$, $[1, 3, 4]$ 同样不可行，因为技能水平为 $5$ 和 $6$ 的学生未被分配到任何班级。

在第三个测试用例中，你可以按如下方式分配学生：$[3, 4, 13, 13, 20], [2, 5, 8, 16, 17]$ 或 $[3, 8, 17], [2, 4, 5, 13, 13, 16, 20]$。这两种划分方式均能得到最小可能的绝对差值。