11881188 SUSTech Online Judge
Problem 1188 --A hard kth smallest number[Hard]

1188: A hard kth smallest number[Hard]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 467  Solved: 47
[Submit][Status][Web Board]

Description

Hong finds that the kth smallest number problem is too easy.  He comes up with a harder problem.

Given N integers A1...An.  Let Bk = |Ai - Aj|(1<=i<j<=N), we can get C(n, 2) Bk. Hong wants to know the median of these defferences.

If C(n, 2) is even, the median is defined as the (C(n, 2) / 2)th smallest number.

Input

The first line will be an integer T (1≤T≤10), which is the number of test cases.  

For each test data:

The first line contains one integer N(1≤N≤10^5).

The next line contains N integers Ai(1≤Ai≤10^9).

Output

For each case, please print the median.

Sample Input

1
4
1 2 3 4

Sample Output

1

HINT

Source

Sorting 

[Submit][Status]