问题描述

在桌子上，有 $N$ 张卡片横向排列着（其中 $N$ 是奇数）。每张卡片上写着一个正整数，从左到右依次记作 $a_i$，表示第 $i$ 张卡片上的数字（$1 \leq i \leq N$）。任意两张卡片上的数字都不相同。卡片按照数字从小到大的顺序从左到右排列。

想象有两个玩家：Snuke（先手）和 Iroha（后手）。他们轮流进行以下操作，直到只剩下两张卡片为止：

操作: 在当前场上的卡片中选择一张卡片拿在手中，并完全消去该卡片的存在。

当所有操作结束时，仍然存在的两张卡片上的数字之差的绝对值作为这个游戏的得分。

这个游戏有如下的额外规则：

• 先手的 Snuke 在自己行动的时候，必须选择放在最中间的卡片。也就是说，在某个时刻剩下 $r$ 张卡片，Snuke 必须选择消去从左数第 $(r+1)/2$ 张卡片。
• 后手的 Iroha 在自己行动的时候，必须选择剩下的卡片中最左边的卡片或者最右边的卡片。

求在 Iroha 最优策略下，游戏的得分是多少。

约束条件

• $N$ 是奇数，$a_i \ (1 \leq i \leq N)$ 是整数
• $3 \leq N \leq 10^{5}$
• $1 \leq a_i \leq 10^{9} \ (1 \leq i \leq N)$
• $a_i < a_j \ (1 \leq i < j \leq N)$

输入

输入从标准输入中得到，具体格式如下：

$N$ $a_1\\ a_2\\ \\cdots\\ a_N$

输出

以一行输出游戏得分。

示例1

3
1 5 100

输出示例1

99

Snuke 可以消去第二张卡片，游戏结束。

示例2

9
3 14 15 20 33 51 59 62 68

输出示例2

45

解释

解释

第三页的正文的第2行“最大値”应为“最小値”，不好意思。

（5/13 21:40 追记）