Minimum Maximum Height Difference
Given N integers representing the heights of N students, you want to divide them into two groups. Your goal is to minimize the maximum height difference within each group. Print this minimum possible maximum difference.
Input
The first line contains an integer N (2 <= N <= 200000). The second line contains N space-separated integers representing student heights (1 <= h_i <= 10^9).
Output
Print a single integer, the minimum possible maximum height difference.
Constraints
2 <= N <= 200000 1 <= h_i <= 10^9
Example 1
5 1 2 5 8 10
4
Groups {1, 2, 5} (diff 4) and {8, 10} (diff 2). Max diff is 4. Another split: {1, 2, 8} (diff 7) and {5, 10} (diff 5). Max diff is 7. Optimal: {1, 2, 5, 8} (diff 7) and {10} (diff 0), max diff 7. Or {1, 2} (diff 1) and {5, 8, 10} (diff 5), max diff 5. Optimal split is {1,2} and {5,8,10}, minimum max
Example 2
4 10 20 30 40
10
Groups {10, 20} (diff 10) and {30, 40} (diff 10). Max diff is 10. Optimal: {10,20} and {30,40}, minimum maximum difference is 10.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 5 8 10
4 10 20 30 40