CF594A.Warrior and Archer

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.

在正式比赛中，本题的题面有所不同，当时裁判组的参考程序存在错误，因此该题被从比赛中移除。这一错误现已修正，当前给出的题目描述及参考解法均符合裁判组在比赛期间的原始意图。

沃瓦（Vova）和列沙（Lesha）是朋友。他们经常在沃瓦家聚会，并在一款名为《古纸莎草：剑墨》（The Ancient Papyri: Swordsink）的电脑游戏中对战。沃瓦总是选择战士作为自己的角色，而列沙则选择弓箭手。之后，他们需分别为各自的角色选定初始位置，然后开始战斗。战士擅长近身格斗，因此沃瓦会尽力使双方角色的初始距离尽可能小；而弓箭手则偏好与敌人保持距离，因此列沙会尽力使初始距离尽可能大。

在 $Ox$ 轴上有 $n$（$n$ 恒为偶数）个可供角色起始站立的位置，其坐标互不相同，记为 $x_1,\,x_2,\,\dots,\,x_n$；两个角色不能占据同一位置。

沃瓦和列沙轮流禁止（ban）尚未被禁止的位置，沃瓦先手。每轮中，其中一人恰好禁止一个尚存的可用位置；被禁止的位置双方均不可使用。他们持续进行此操作，直至仅剩两个位置为止（因此总共进行 $n-2$ 轮操作）。此后，沃瓦的角色占据剩余两个位置中坐标较小的那个，列沙的角色占据坐标较大的那个，战斗随即开始。

沃瓦和列沙已厌倦了每次战斗前都要手动选择位置的游戏环节，于是他们请求你（《古纸莎草：剑墨》的开发者）编写一个模块，自动计算：当沃瓦与列沙均以最优策略进行位置禁止时，战士与弓箭手的初始战斗距离是多少。

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 ≤ 109), giving the coordinates of the corresponding positions.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 200\,000$，且 $n$ 为偶数）—— 表示初始可用的位置数量。
第二行包含 $n$ 个互不相同的整数 $x_1,\,x_2,\,\dots,\,x_n$（$0 \leq x_i \leq 10^9$），表示对应位置的坐标。

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

输出战斗开始时战士与弓箭手之间的距离，前提是沃瓦和列沙均采取最优策略。

In the first sample one of the optimum behavior of the players looks like that:

1. Vova bans the position at coordinate 15;
2. Lesha bans the position at coordinate 3;
3. Vova bans the position at coordinate 31;
4. 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.

在第一个样例中，双方玩家的一种最优策略如下：

1. Vova 禁用坐标为 15 的位置；
2. Lesha 禁用坐标为 3 的位置；
3. Vova 禁用坐标为 31 的位置；
4. Lesha 禁用坐标为 1 的位置。

经过上述操作后，仅剩位置 0 和 7，它们之间的距离为 7。

在第二个样例中，仅有两个可能的位置，因此不会发生任何禁用操作。