Problem L
Large Differences

Tom has $N$ objects of various heights, where object $i$ has height $H_ i$. He wants to line them up in a row and take a photo of them. Since he likes chaos, he wants the photo to look as disorderly as possible. In particular, given an arrangement, he will calculate the minimum difference in heights, $X$, between every pair of adjacent objects in the row.

Could you help him find the maximum possible value of $X$? Formally, find the maximum possible value of $\min _{1 \leq i \leq N - 1}|p_{i + 1} - p_ i|$, for all possible permutations $p_1, \dots , p_ N$ of $H_1, \dots , H_ N$.


The first line of input consists of a single positive integer $N$ $(2 \leq N \leq 500000)$.

The next line contains $N$ integers $H_1, H_2, \dots , H_ N (1 \leq H_ i \leq 10^9)$.


Output a single integer, the maximum possible value of $X$ as described above.

Sample Input 1 Sample Output 1
2 6 10 2
Sample Input 2 Sample Output 2
2 6 7 3 8

Please log in to submit a solution to this problem

Log in