题目描述
在城堡里面游玩回来以后，小A 和小B 还是准备继续备赛。
老师最近给他们考了这样一个问题：有N 个正整数$a_1, a_2, \dots, a_N$, 对这些正整数任意2 个做差以后求绝对值。例如，我们对$a_i$ 和 $a_j$ 作差，可以得到 $|a_i − a_j |$。显然，这样的差一共有 $\frac{N(N−1)}{2}$ 个。
我们令$M= \frac{N(N−1)}{2}$ ，输入的 $N$ 保证 $M$ 一定是一个偶数。老师现在想让小A 和 小B 求出所有这些绝对值里面从小到大第 $\frac{M}{2}$ 小的数。
小A 和小B 想了很久，想请你来帮助他们。
注意：在数学中，我们规定一个负数的绝对值就是把它的负号去掉以后的数，例如，$| − 5| = 5$, 而0 和正数的绝对值还是它本身。
输入
输入的第一行是一个正整数N，表示数的个数。
接下来N 行，每行一个正整数，表示$a_i$。
输出
输出所有绝对值中从小到大第$\frac{M}{2}$ 小的数。
样例输入输出
提示
样例中，我们总共有4 个数，求出来的绝对值分别是：|1 − 10| = 9, |1 − 2| = 1, |1 − 3| = 2, |10 − 2| = 8, |10 − 3| = 7, |2 − 3| = 1，从小到大排序以后就是1，1，2，7，8，9，M 是3。所以第M 小的数是2。
【数据范围】
对于所有的数据，保证$1 \le N \le 10^5, 1 \le a_i ≤ 10^9$。
数据编号|数据范围
--|--
1-3 |$N \le 50, a_i \le 10^3 $
4-5 |$N \le 10^3, a_i \le 10^3 $
6-7 |$N \le 5 \times 10^3, a_i \le 10^3 $
8-10|$ N \le 10^5, a_i \le 10^9 $