410727: GYM104094 C Tournament

The linguistic game "Hat" is played by several pairs of players. Also there should be one host of the game.

A teacher plans to organize a "Hat" tournament in their class consisting of $$$n$$$ students, where $$$n$$$ is odd number. In order to do this he wants to split students into pairs and leave one student to be the host.

Number students from $$$1$$$ to $$$n$$$. Student number $$$i$$$ is known to have a skill value of $$$a_i$$$ in the "Hat" game. Skill of a pair of students is defined as the sum of their individual skills.

In order for the tournament to be as fair as possible the teacher wants the difference between the maximum and minimum skills of resulting pairs to be as small as possible. Help the teacher to choose the host and split other $$$n - 1$$$ students into pairs in order to achieve the desired goal.

The first line of input contains an integer $$$n$$$ — the number of students in the class ($$$3 \le n \le 5 \cdot 10^5$$$, $$$n$$$ is guaranteed to be odd).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Output one number — the smallest possible difference between maximum and minimum skills of pairs participating in the tournament.

5
1 2 3 5 9

1