In the official contest this problem has a different statement, for which jury's solution was working incorrectly, and for this reason it was excluded from the contest. This mistake have been fixed and the current given problem statement and model solution corresponds to what jury wanted it to be during the contest.

Vova and Lesha are friends. They often meet at Vova's place and compete against each other in a computer game named The Ancient Papyri: Swordsink. Vova always chooses a warrior as his fighter and Leshac chooses an archer. After that they should choose initial positions for their characters and start the fight. A warrior is good at melee combat, so Vova will try to make the distance between fighters as small as possible. An archer prefers to keep the enemy at a distance, so Lesha will try to make the initial distance as large as possible.

There are n (n is always even) possible starting positions for characters marked along the Ox axis. The positions are given by their distinct coordinates x_1, x_2, ..., x_{n}, two characters cannot end up at the same position.

Vova and Lesha take turns banning available positions, Vova moves first. During each turn one of the guys bans exactly one of the remaining positions. Banned positions cannot be used by both Vova and Lesha. They continue to make moves until there are only two possible positions remaining (thus, the total number of moves will be n - 2). After that Vova's character takes the position with the lesser coordinate and Lesha's character takes the position with the bigger coordinate and the guys start fighting.

Vova and Lesha are already tired by the game of choosing positions, as they need to play it before every fight, so they asked you (the developer of the The Ancient Papyri: Swordsink) to write a module that would automatically determine the distance at which the warrior and the archer will start fighting if both Vova and Lesha play optimally.


-----Input-----

The first line on the input contains a single integer n (2 ≤ n ≤ 200 000, n is even) — the number of positions available initially. The second line contains n distinct integers x_1, x_2, ..., x_{n} (0 ≤ x_{i} ≤ 10^9), giving the coordinates of the corresponding positions.


-----Output-----

Print the distance between the warrior and the archer at the beginning of the fight, provided that both Vova and Lesha play optimally.


-----Examples-----
Input
6
0 1 3 7 15 31

Output
7

Input
2
73 37

Output
36



-----Note-----

In the first sample one of the optimum behavior of the players looks like that:  Vova bans the position at coordinate 15;  Lesha bans the position at coordinate 3;  Vova bans the position at coordinate 31;  Lesha bans the position at coordinate 1. 

After these actions only positions 0 and 7 will remain, and the distance between them is equal to 7.

In the second sample there are only two possible positions, so there will be no bans.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import os\nimport random\nimport sys\n# from typing import List, Dict\n#\n#\n# class Int:\n#     def __init__(self, val):\n#         self.val = val\n#\n#     def get(self):\n#         return self.val + 111\n#\n# class Unique:\n#     def __init__(self):\n#         self.s = set()\n#\n#     def add(self, val : int):\n#         self.s.add(val)\n#\n#     def __contains__(self, item : int) -> bool:\n#         return self.s.__contains__(item)\n#\n# def ceil(top : int, bottom : int) -> int:\n#     return (top + bottom - 1) // bottom\n#\n# def concat(l : List[int]):\n#     return "".join(map(str, l))\n#\n# def get(d : Dict[int, str], val : int) -> Dict[int, str]:\n#     return d[val]\n\n\n#guy who wants small moves first\n#then guy who wants large moves\n\n#so lets say we have 4 positions\n# 1, 2, 3, 4\n#small wants to ban edges, because if he bans 2 or 3 he is fucked\n#so he bans 1\n# and we have 2, 3, 4\n# then large bans middle so we have 2, 4 and the ans is 2\n# 0, 1, 2, 3, 4, 5, 6, 7\n# 0, 1, 2, 3, 4, 5, 6\n# 0, 1, 2, 3, 5, 6\n# 0, 1, 2, 3, 5\n# 0, 1, 3, 5\n# 0, 1, 3\n# 0, 3\n\n\n# 0, 1, 2, 3, 4, 5, 6, 7\n# 0, 4\n\n# # 0, 3\n\n\n#1 5 9 19 21 22\n#  5 9 19 21 22\n#  5 19 21 22\n#  19 21 22\n\n\n# 0, 1, 3, 7, 15\n# 0, 1, 7, 15\n# 0, 1, 7\n# 0, 7\ndef slowsolve(a):\n    a.sort()\n    small = True\n    while len(a) > 2:\n        if small:\n            if a[1] - a[0] > a[-1] - a[-2]:\n                a.pop(0)\n            else:\n                a.pop()\n            small = False\n        else:\n            a.pop(len(a) // 2)\n            small = True\n\n    return a[1] - a[0]\n\n\ndef solve(a):\n    a.sort()\n    candelete = len(a) // 2 - 1\n    res = 10 ** 18\n    for leftdelete in range(0, candelete + 1):\n        leftrem = leftdelete\n        rightrem = leftdelete + candelete + 1\n        res = min(res, a[rightrem] - a[leftrem])\n    return res\n\n\n\ndef prt(l): return print(\' \'.join(l))\ndef rv(): return map(int, input().split())\ndef rl(n): return [list(map(int, input().split())) for _ in range(n)]\nif os.path.exists("test.txt"): sys.stdin = open("test.txt")\n\nn, = rv()\na, = rl(1)\n\n# a = sorted([random.randrange(10**2) for _ in range(6)])\n# print(a)\n# print(solve(a), slowsolve(a))\nprint(solve(a))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14201