在正式竞赛中,这个问题有不同的说法,评审团的解决方案工作不正确,因此被排除在竞赛之外。该错误已得到修复,当前给出的问题陈述和模型解决方案符合评审团在比赛期间的预期。
Vova 和 Lesha 是朋友。他们经常在 Vova 的住处见面,并在一款名为《Thecient Papyri: Swordsink》的电脑游戏中相互竞争。 Vova 总是选择战士作为他的战士,而 Leshac 选择弓箭手。之后他们应该为自己的角色选择初始位置并开始战斗。战士擅长近战,所以Vova会尽量拉近战士之间的距离。弓箭手更喜欢与敌人保持一定的距离,因此莱莎会尝试让初始距离尽可能大。
沿 Ox 轴标记的字符有 n 个(n 始终为偶数)可能的起始位置。位置由其不同的坐标 x1、x2、...、xn 给出,两个字符不能出现在同一位置。
Vova 和 Lesha 轮流禁止可用位置,Vova 首先移动。在每一回合中,其中一个人会恰好禁止剩余位置中的一个。 Vova 和 Lesha 均不能使用禁用位置。他们继续移动,直到只剩下两个可能的位置(因此,移动总数将为 n - 2)。之后,Vova 的角色占据坐标较小的位置,Lesha 的角色占据坐标较大的位置,大家开始战斗。
Vova 和 Lesha 已经厌倦了选择位置的游戏,因为他们需要在每次战斗前玩这个游戏,所以他们要求你(《古代纸莎草纸:Swordsink》的开发者)编写一个模块,在 Vova 和 Lesha 都发挥最佳的情况下,自动确定战士和弓箭手开始战斗的距离。
输入
输入的第一行包含一个整数 n(2 ≤ n ≤ 200 000,n 为偶数)——最初可用的位置数。第二行包含 n 个不同的整数 x1, x2, ..., xn (0 ≤ xi ≤ 109),给出相应位置的坐标。
输出
打印战斗开始时战士和弓箭手之间的距离,前提是 Vova 和 Lesha 都处于最佳状态。
示例
输入 #1
6 0 1 3 7 15 31
输出 #1
7
输入 #2
2 73 37
输出 #2
36
注意
在第一个示例中,玩家的最佳行为之一如下所示:
1、Vova禁止坐标15的位置;
2. Lesha禁止坐标3处的位置;
3、Vova禁止坐标31处的位置;
4. Lesha禁止坐标1处的位置。
在这些操作之后,仅保留位置 0 和 7,并且它们之间的距离等于 7。
在第二个示例中,只有两个可能的位置,因此不会出现禁令。