Doubles
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.5 seconds
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 spaceseparated 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

Sample Input 1
4 3 2 9 5
Sample Output 1
3

Sample Input 2
6 6 2 5 5 3 7
Sample Output 2
1