Background

在城堡里面游玩回来以后，小 $A$ 和小 $B$ 还是准备继续备赛。

老师最近给他们考了这样一个问题：有 $N$ 个正整数 $a_1, a_2, .., a_N$ , 对这些正整数任意 $2$ 个做差以后求绝对值。例如，我们对 $a_i$ 和 $a_j$ 作差，可以得到 $|a_i − a_j |$。显然，这样的差一共有 $N*(N−1) /2$ 个。

我们令 $M = N*(N−1)/2$ ，输入的 $N$ 保证 $M$ 一定是一个偶数。老师现在想让小 $A$ 和小 $B$ 求出所有这些绝对值里面从小到大第 $M/2$ 小的数。 小 $A$ 和小 $B$ 想了很久，想请你来帮助他们。

注意：在数学中，我们规定一个负数的绝对值就是把它的负号去掉以后的数，例如，$| − 5| = 5$ , 而 $0$ 和正数的绝对值还是它本身。

Input

输入的第一行是一个正整数 $N$，表示数的个数。

接下来 $N$ 行，每行一个正整数，表示 $a_i$。

Output

输出所有绝对值中从小到大第 $M/2$ 小的数。

Samples

4
1
10
2
3

2

Limitation

样例中，我们总共有 $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$ 是 $6$。所以第 $M/2$ 小的数是 $2$。

对于所有的数据，保证 $1 ≤ N ≤ 10^5 , 1 ≤ a_i ≤ 10^9$。

对于数据编号

$1∼3$ ，有 $N ≤ 50, a_i ≤ 10^3$

$4∼5$ ，有 $N ≤ 10^3 , a_i ≤ 10^3$

$6∼7$ ，有 $N ≤ 5 × 10^3 , a_i ≤ 10^3$

$8∼10$ ，有 $N ≤ 10^5 , a_i ≤ 10^9$