Description

给定 $N$ 个数 $X_1 , X_2 ,…, X_N$，计算每一 对数字的差：$|X_i -X_j |，1≤i ＜j ≤N$。请尽快找到差的中位数！ 注意，在这个问题中，中位数被定义为第 $m /2$ 个数，$m$ 为差的数量。

Format

Input

输入由几个测试用例组成。每个测试用例的第 $1$ 行都为 $N$ 。

然后给出 $N$ 个数字，表示$X_1 , X_2 ,…, X_N$ $（ X_i ≤10^9 ，3≤N ≤10^5）。$

Output

对于每个测试，都单行输出差的中位数。

Samples

4
1 3 2 4
3
1 10 2

1
8

来源

POJ3579