Doubles

Toddy is organising a doubles tournament for his favourite fighting game, Super Bash Sisters, and $N$ individual players have signed up.

Since this is a doubles tournament, he needs to group the players into teams of two. To make the matches more exciting, he would like to minimise the difference in strength between the strongest and weakest team.

Each player has a skill level $s_i$, and the strength of a team is the sum of skill levels of both players in that team.

Please help find the minimum difference between the strongest and weakest team that can be achieved by pairing up players optimally.

Input

The first line contains a single integer, $N$, the number of players in the tournament.

The second line contains $N$ space-separated integers, $s_1, s_2, \dots, s_N$, the skill levels of each player in the tournament.

Output

You should output a single integer – the minimum possible difference in strength between the strongest and weakest team if players are paired up optimally.

Constraints

For all subtasks:

• $4 \le N \le 1000$, and $N$ is even
• $1 \le s_i \le 1000$

Subtasks

• Subtask 1 (25%): $N = 4$
• Subtask 2 (25%): $N \le 8$
• Subtask 2 (25%): $N \le 16$
• Subtask 2 (25%): $N \le 1000$