Description

给定N个数字，X1，X2。。。XN，让我们计算每对数字的差：∣Xi-Xj∣（1≤i＜j≤N）。我们可以通过这项工作得到C（N，2）个差，任务是尽快找到所有差值的中位数

Format

Input

第一行：N

第二行：n个用空格分隔的数字：X1，X2，X3...XN

Output

所有差值的中位数

Sample 1

Input

3
1 10 2

Output

8

Source

对于50% \(n\) \(\leq\) \(1000\)
对于100% \(n\) \(\leq\) \(200000\)