Fence Height

Cows have strong feelings about how high a fence should be. A cow wants the fence high enough that she feels safe and protected, but not so high that she cannot see over it and moo at passing cars. Though a cow could stand on her tip-hooves or squat down to reach the right height, she naturally wants the fence to be the right height in the first place. Each of the $N$ ($1 \le N \le 10{,}000$) cows expresses a height preference ($1 \le \text{preference} \le 10{,}000$), which may vary from cow to cow.

Farmer John has a predicament. As a man of great esthetics, he wants his fence to be a uniform height everywhere. But as a man of great empathy, he sincerely wants to satisfy his cows. (Or maybe he is just selfish and knows the cows would give more milk if they got what they wanted.)

To compromise, he builds portions of the fence using posts of different heights, so that a majority (strictly more than half) of the cows are satisfied. A cow is satisfied if some part of the fence is at her height preference. Farmer John wants to minimize the range of post heights used, that is, the difference between the highest and lowest post. Help him do that.

The height of a fence post determines the fence height. The fence is not a continuous function connecting two posts of different heights.

The first line contains an integer $N$. Each of the next $N$ lines contains one cow's fence post height preference, an integer.

Print a single integer, the minimum range of fence post heights.

Farmer John can use fence posts of height 1 and 3 to satisfy 2 of the 3 cows. The range is $3-1=2$.