토너먼트

언어 게임 "Hat"은 여러 쌍의 플레이어가 함께 하는 게임이다. 게임에는 진행자(호스트) 한 명도 필요하다.

선생님은 학급 학생 $n$명으로 "Hat" 토너먼트를 열려고 한다. $n$은 홀수다. 선생님은 학생들을 쌍으로 나누고, 한 명은 진행자로 남기려 한다.

학생에게 1부터 $n$까지 번호를 붙인다. $i$번 학생의 "Hat" 기술 값은 $a_i$다. 한 쌍의 기술 값은 두 학생 기술 값의 합이다.

토너먼트를 최대한 공정하게 만들기 위해, 쌍들의 기술 값 중 최댓값과 최솟값의 차이를 가능한 한 작게 하려 한다. 진행자를 고르고 나머지 $n-1$명을 쌍으로 나누어 이 목표를 이루는 방법을 찾아라.

첫째 줄에 학생 수 $n$이 주어진다 ($3 \le n \le 5 \cdot 10^5$, $n$은 홀수다).

둘째 줄에는 정수 $a_1, a_2, \ldots, a_n$이 공백으로 구분되어 주어진다 ($1 \le a_i \le 10^9$).

쌍들의 기술 값에서 최댓값과 최솟값의 차이가 가능한 가장 작을 때의 값을 한 줄에 출력한다.