Minimal Height Difference After Tree Pruning

Given an even number n of trees, each with a certain height, you are required to remove exactly n/2 trees in such a way that the difference between the tallest and shortest trees among the remaining ones is minimized.

After removing n/2 trees, the remaining trees count will be n/2. If we sort the tree heights in non-decreasing order as \(h_1, h_2, \dots, h_n\), then the problem reduces to choosing a contiguous block of n/2 trees. The minimal height difference is defined by the following formula:

[ \min_{1 \leq i \leq n/2+1}\left(h_{i+n/2-1} - h_{i}\right) ]

Your task is to compute and output this minimal possible difference.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains a single integer n (an even number), representing the number of trees.
2. The second line contains n space-separated integers, where each integer represents the height of a tree.

outputFormat

Output a single integer to stdout representing the minimal possible difference between the tallest and shortest tree among the remaining trees after removing exactly n/2 trees.

6
2 9 3 4 7 6

2