울타리 높이

소들은 울타리 높이에 대한 뚜렷한 선호가 있다. 소는 안전하고 보호받는다고 느낄 만큼 울타리가 높기를 원하지만, 너무 높아서 울타리 너머를 볼 수 없고 지나가는 차에 울 수 없을 정도면 안 된다. 소는 발끝으로 서거나 쪼그려 앉아서 알맞은 높이에 맞출 수 있지만, 애초에 울타리가 알맞은 높이이기를 바란다. $N$마리($1 \le N \le 10{,}000$)의 소가 각각 높이 선호도($1 \le \text{선호도} \le 10{,}000$)를 밝히며, 선호도는 소마다 다를 수 있다.

농부 존은 난처한 처지에 있다. 미적 감각이 뛰어난 사람으로서 울타리를 어디서나 같은 높이로 짓고 싶지만, 공감 능력이 뛰어난 사람으로서 소들의 요구도 진심으로 들어주고 싶다. (혹은 그냥 이기적이어서, 소들이 원하는 것을 받으면 우유를 더 많이 낸다는 것을 알고 있을 뿐일 수도 있다.)

타협안으로, 존은 서로 다른 높이의 기둥을 섞어 울타리의 일부를 세우고, 과반(절반보다 많은 수)의 소를 만족시킨다. 소는 울타리의 어느 부분이든 자신의 선호 높이에 해당하면 만족한다. 존은 사용하는 기둥 높이의 범위, 즉 가장 높은 기둥과 가장 낮은 기둥의 높이 차이를 최소로 하고 싶어 한다. 그 최솟값을 구하라.

울타리의 높이는 기둥의 높이로 정해진다. 서로 다른 높이의 두 기둥 사이를 잇는 연속 함수가 아니다.

첫째 줄에 정수 $N$이 주어진다. 이어지는 $N$개의 줄에는 소 한 마리당 울타리 높이 선호도를 나타내는 정수가 한 줄에 하나씩 주어진다.

사용한 기둥 높이 범위의 최솟값을 정수 하나로 출력한다.

농부 존은 높이가 1과 3인 기둥을 사용하면 소 3마리 중 2마리를 만족시킬 수 있다. 범위는 $3-1=2$이다.