IQ

Interview

Time limit1sMemory limit64 MB

Summary

Pair 2n numbers into n pairs so the difference between the largest and smallest pair sums is minimized, and print that difference.

Level: Easy3 of 10
Topics: Sorting, Greedy, Brute force, Array
Solved: No attempts yet

Problem

$2n$ newbie students came to competitive programming practice. Each student is characterized by his IQ level: the $i$ -th student has IQ $a\_i$ .

The coach wants to break students up into teams of two people. Each team is characterized by a team IQ that is equal to the sum of the team members IQ levels. For example, if a team is formed from students $i$ and $j$ , the team IQ is $a\_i + a\_j$ . One team is stronger than the other if its team IQ is greater.

By the coach's opinion, practice will be much more productive if the difference between team IQs of the strongest and the weakest team is as small as possible. Help the coach determine the minimum value $A$ for which it is possible to form teams in such a way that difference of team IQs between the strongest and the weakest team is equal to $A$ .

Input

The first line contains integer $n$ ( $1 \le n \le 100$ ).

The second line contains $2n$ integers, the $i$ -th of which is equal to the IQ of the $i$ -th student $a\_i$ ( $1 \le a\_i \le 200$ , $1 \le i \le 2n$ ).

Output

Output the minimum value $A$ for which the forming of teams is possible.

Examples1

Example 1
Input
```
3
100 100 89 140 102 150
```
Expected output
```
38
```