Tournament

Interview

Time limit1sMemory limit1024 MB

Summary

Remove one student as host and pair the other n-1 students so that the gap between the largest and smallest pair sums is as small as possible.

Level: Medium5 of 10
Topics: Sorting, Greedy, Prefix sum
Solved: No attempts yet

Statement

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. To do this, the teacher wants to split the students into pairs and leave one student to be the host.

Number the students from $1$ to $n$ . Student $i$ has a "Hat" skill value of $a_i$ . The skill of a pair is the sum of the two students' skill values.

To make the tournament as fair as possible, the teacher wants the difference between the maximum and minimum pair skills to be as small as possible. Help the teacher choose the host and split the other $n-1$ students into pairs to reach this goal.

Input

The first line contains an integer $n$ , the number of students ( $3 \le n \le 5 \cdot 10^5$ , $n$ is odd).

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

Output

Print one number: the smallest possible difference between the maximum and minimum skills of the pairs.

Examples1

Example 1
Input
```
5
1 2 3 5 9
```
Expected output
```
1
```