CF594A Warrior and Archer

在正式比赛中，本题的题面与现在不同，导致评测程序的解法不正确，故被排除出比赛。现在已修正了题目叙述与参考解答，使其符合评测程序在比赛时的本意。 Vova 和 Lesha 是朋友。他们经常在 Vova 家见面，并相互切磋一款叫做 The Ancient Papyri: Swordsink 的电脑游戏。Vova 总是选择战士，而 Lesha 则选择弓箭手。之后，他们需要为各自的角色选择初始位置，开始战斗。战士擅长近战，因此 Vova 会尽量让双方的距离尽可能小；弓箭手喜欢拉开距离，因此 Lesha 会尽量让初始距离尽可能大。 共有 $n$ 个可能的初始位置（$n$ 总是偶数），这些位置沿着 $Ox$ 轴被标记。各位置通过它们互不相同的坐标 $x_1, x_2, ..., x_n$ 给出，两个角色不能选择同一个位置。 Vova 和 Lesha 轮流轮流禁用可用的位置，Vova 先手。每次轮到某人时，必须从剩余位置中禁掉恰好一个位置。被禁用的位置不能被 Vova 或 Lesha 选用。他们持续轮流禁用，直到只剩下两个可用位置为止（因此总共会禁用 $n-2$ 个位置）。最后，Vova 的角色选择较小坐标的位置，Lesha 的角色选择较大坐标的位置，然后开始战斗。 选择位置的“游戏”让二人感到厌烦，因为每次战斗前都要重复进行，因此他们请你（这款游戏 The Ancient Papyri: Swordsink 的开发者）写一个模块，自动判断如果两人都采用最优策略，战士和弓箭手开战时的初始距离是多少。

第一行输入一个整数 $n$（$2 \leq n \leq 200000$，$n$为偶数），表示一开始可用的位置数量。 第二行输入 $n$ 个互不相同的整数 $x_1, x_2, ..., x_n$（$0 \leq x_i \leq 10^9$），表示每个位置的坐标。

输出若双方都采取最优策略时，战士与弓箭手开战的初始距离。

以第一个样例为例，双方最优行为之一如下： 1. Vova 禁用坐标为 $15$ 的位置； 2. Lesha 禁用坐标为 $3$ 的位置； 3. Vova 禁用坐标为 $31$ 的位置； 4. Lesha 禁用坐标为 $1$ 的位置。 操作结束后，只剩下坐标为 $0$ 和 $7$ 的位置，二者的距离为 $7$。 第二个样例中只剩下两个位置，因此不需要禁用。 由 ChatGPT 5 翻译