Chia lớp theo median

Có $2n$ học sinh, học sinh thứ $i$ có mức năng lực $a_i$. Các mức năng lực không nhất thiết phải khác nhau.

Ta định nghĩa mức năng lực của một lớp là số median của các mức năng lực của học sinh trong lớp đó. Với một mảng gồm $2k+1$ phần tử, median là phần tử ở vị trí thứ $k+1$ sau khi sắp xếp không giảm.

Bạn cần chia toàn bộ $2n$ học sinh vào đúng $2$ lớp sao cho:

• Mỗi học sinh thuộc đúng một lớp.
• Số lượng học sinh trong mỗi lớp là số lẻ (không chia hết cho $2$).
• Số học sinh giữa hai lớp có thể bằng nhau hoặc khác nhau.

Trong tất cả các cách chia hợp lệ, hãy tìm giá trị nhỏ nhất của $|m_1-m_2|$, trong đó $m_1$ và $m_2$ là mức năng lực (median) của hai lớp.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$.
  • Dòng thứ hai chứa $2n$ số nguyên $a_1,a_2,\dots ,a_{2n}$ — mức năng lực của các học sinh.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất — giá trị nhỏ nhất của $|m_1-m_2|$.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le {10}^5$
• $1\le a_i\le {10}^9$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Ví dụ