AT_iroha2019_day3_f 闇のカードゲーム

桌上整齐地摆放着 $N$ 张卡片（$N$ 为奇数），每张卡片上有一个正整数。卡片按整数从小到大排列，位于第 $i$ 张卡片上的整数为 $a_i$。不同的卡片上不会有相同的整数。 すぬけ君和いろはちゃん轮流进行操作，直到桌面上仅剩下 2 张卡片。すぬけ君作为先手，双方依次进行以下操作： **操作**：从当前桌面上选择一张卡片将其拿走并移除。 游戏结束时，剩下两张卡片上的整数差的绝对值即为游戏的得分。 在进行游戏时，先手和后手需遵循以下规则： - すぬけ君（先手）必须选择当前桌面上居中的那张卡片。假设当前剩余卡片数为 $r$，他必须拿走第 $(r+1)/2$ 张卡片。 - いろはちゃん（后手）必须从剩余卡片中选择最左或最右的一张。 假设いろはちゃん始终以最优策略行事以使得游戏得分最小化，求出最终的游戏得分。

输入通过标准输入给出，格式如下： > $ N $ $ a_1\ a_2\ \cdots\ a_N $

输出游戏结束时的得分，即两张剩余卡片上整数差的绝对值。

- $N$ 是奇数，$3 \leq N \leq 10^5$。 - 卡片上的整数 $a_i$ 满足 $1 \leq a_i \leq 10^9$。 - 所有 $a_i$ 均为整数且互不相同。 ## 示例解释 すぬけ君在第一回合可能会选择从左数的第 2 张卡片，然后游戏结束。 **本翻译由 AI 自动生成**