题目描述

“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