406071: GYM102254 D Donimo's

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Donimo'stime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Everyone knows Tuesday is Donimo's Day! Probably not the best pizza around, but people from the International Math-addicted Engineers (IME) like the discounts from Tuesday so much that they are willing to improve their method of dividing the pizza slices.

This Tuesday a total of $$$n$$$ people ordered $$$2 \times n$$$ pizza slices from Donimo's. The slices are not cut exactly equal and every person will eat 2 slices each. They want the division to be the most fair as possible.

The most fair division is the one that the difference between the amounts of pizza eaten by the person that eaten the most and the person that eaten the least is minimum possible.

Your task is to calculate the most fair division and print the difference between the amounts pizza eaten by the person that ate the most and the person that ate the least.

Input

The first line contains one integer, $$$n$$$ ($$$2 \le n \le 10^4)$$$ — the number of people ordering pizza.

The second line contains $$$2 \times n$$$ integers, $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the size of each slice.

Output

Print the minimum difference between the amounts pizza eaten by the person that eaten the most and the person that ate the least.

ExamplesInput
2
1 4 3 2
Output
0
Input
4
5 1 1 4 3 2 11 3
Output
6

加入题单

上一题 下一题 算法标签: