Young Energy Is Not Enough

Time limit1sMemory limit256 MB

Summary

Partition 3N ages into N triples; each triple's energy is its median age. Minimize the spread between the largest and smallest median.

Level: Medium6 of 10
Topics: Sorting, Greedy, Binary search, Array
Solved: No attempts yet

Problem

The reality survival show is looking for the best street algorithm crew in South Korea. $3N$ college students who are said to be good at algorithms from all over the country have joined, and they will form $N$ crews of 3 to compete in street algorithm battles.

But computer science students have always coded alone, so the production team has to make the crews...

The production team is worried that a crew might lack young energy. So the production team will form the $N$ crews with the following in mind.

Call the median age of a crew's members, that is, the age of the second oldest of the three members, the crew's energy.
The production team must minimize the difference in energy between the crew with the highest energy and the crew with the lowest energy.

Find this minimized value.

Input

The first line gives $N$ . There are $3N$ participants in total.

The second line gives $3N$ integers separated by spaces. The $i$ -th integer $a_i$ is the age of the $i$ -th participant.

Output

Form the $N$ crews from the $3N$ participants appropriately, and output the energy difference when the difference in energy between the crew with the highest energy and the crew with the lowest energy is minimized.

Constraints

$1 \le N \le 100\,000$
$1 \le a_i \le 100\,000\,000$

Examples1

Example 1
Input
```
2
21 22 23 24 25 26
```
Expected output
```
1
```