Large Differences (Problem L, CS3233 Midterm Contest 2024, 2024)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement
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 - p_{i+1}|$ for all possible permutations $p_1, \dots, p_N$ of $H_1, \dots, H_N$.

# Input

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

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

# Sample Input #1
```
4
2 6 10 2
```
# Sample Output #1
```
4
```
# Sample Input #2
```
5
2 6 7 3 8
```
# Sample Output #2
```
4
```

Sample inputs:
4
2 6 10 2

5
2 6 7 3 8

Sample outputs:
4

4

# Solution Analysis

Sort the array and suppose $ a_1 \leq a_2 \leq \cdots \leq a_n $. Consider 2 cases.

**Case 1**: $ n = 2k $.

Note that for any $ k+1 $ elements of $ a $, there must be two which are adjacent. Thus among $ a_1, \ldots, a_{k+1} $, there are two of them which are adjacent. Thus there is an adjacent difference which is at most $ a_{k+1} - a_1 $.

By repeatedly using the same logic, we can conclude that there is an adjacent difference which is at most  
$ \min(a_{k+1} - a_1, a_{k+2} - a_2, \ldots, a_{2k} - a_k) $.

We can achieve equality with the permutation  
$ (a_{k+1}, a_1, a_{k+2}, a_2, \ldots, a_{2k}, a_k) $.

**Case 2**: $ n = 2k + 1 $.

We use the same idea: there can be at most one set of $ k+1 $ elements of $ a $ where no two are adjacent. As such, there is an adjacent difference which is at most the second smallest among  
$ (a_{k+1} - a_1, a_{k+2} - a_2, \ldots, a_{2k+1} - a_{k+1}) $.

We now show that equality can be achieved. Suppose the smallest is $ a_{k+i} - a_i $. Then at positions  
$ 1, 3, \ldots, 2k+1 $ we put $ a_i, a_{i+1}, \ldots, a_{k+i} $ in that order, and in positions  
$ 2, 4, \ldots, 2k $ we put $ a_{k+i+1}, a_{k+i+2}, \ldots, a_{2k+1}, a_1, a_2, \ldots, a_{i-1} $ in that order.


Special judge (C++ scorer):