题目描述

“OI-Fitter健身训练营”的总教练正在为训练的组织问题发愁。按照流程安排，营员们2人一组进行训练，但悬殊的个体差异让分配队伍的问题变得棘手。
为了评估营员之间差异的大小，总教练设立了这样一个指标：设营员共有$N$名，每个人的健壮程度设为一个正整数$X_i, i = 1,2 \cdots N$。将这$N$个数两两求差并取绝对值，可得到如下的$M = \text{C}(N, 2)$个数：
$\lvert X_s - X_t \rvert , 1 \le s < t \le N$
最终的“差异指标”设为这$M$个数的中位数。若$M$为偶数，则中位数视为第$M / 2$小的数。
现给出营员的数量$N$和每人的健壮程度，请你帮总教练求出他们的“差异指标”。

输入格式

每个测试文件含3～5组测试数据，以文件结束符（EOF）表示输入结束。
对于每组数据：
第一行是一个正整数$N$；
第二行是$N$个正整数，第$i$个数为$X_i$。
30%的数据：$3 \le N \le 1000$
100%的数据：$3 \le N \le 10^5, \quad 1 \le X_i \le 10^9$

输出格式

对于每组测试数据，输出一行表示答案。

样例

input

4
1 3 2 4
3
1 10 2

output

1
8

限制

Time limit: 1 sec
Memory limit: 128 megabytes

来源

From PKU Online Judge