Một chương trình thực tế nổi tiếng tên là Những Cặp Đôi Khác Thường đã được ra mắt trong thành phố. Theo quy tắc của chương trình, những người tham gia được ghép đôi theo một cách lạ lùng: với số lượng người là chẵn, tất cả người tham gia đều phải được ghép thành các cặp. Petya có một mảng gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\). Biết rằng \(n\) là số chẵn. Petya phải chia những người tham gia (các con số) thành đúng \(\frac{n}{2}\) cặp \((a_{p_1}, a_{q_1}), (a_{p_2}, a_{q_2}), \dots, (a_{p_{\frac{n}{2}}}, a_{q_{\frac{n}{2}}})\). Mỗi chỉ số (vị trí trong mảng) chỉ được nằm trong tối đa một cặp. Đối với một cặp \((x, y)\), độ chênh lệch của nó được định nghĩa là \(|x - y|\). Petya muốn tạo ra các cặp đôi khác thường sao cho độ chênh lệch lớn nhất giữa tất cả các cặp là nhỏ nhất có thể. Hãy xác định giá trị nhỏ nhất có thể của độ chênh lệch lớn nhất này.
Đầu vào:
Mỗi bài kiểm tra bao gồm nhiều bộ test (test cases).Dòng đầu tiên chứa một số nguyên \(t\) — số lượng bộ test.
Mô tả của các bộ test theo sau đó.
Dòng đầu tiên của mỗi bộ test chứa một số chẵn \(n\) — độ dài của mảng \(a\).
Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) — các phần tử của mảng \(a\).
Đầu ra: Với mỗi bộ test, in ra một số duy nhất — độ chênh lệch lớn nhất nhỏ nhất có thể giữa các phần tử trong các cặp.