配点: 100 点
問題文
在桌子上, N 卡片水平排列(但是 N 是奇数)。每张牌都有一个正整数 1 它们是从左边开始一一写的。 i 番目 (1 \leq i \leq N) 卡上写入的整数是 a_i 。不同的卡上不能写入相同的整数。此外,卡片按照所写整数的升序从左到右排列。
Snuke君和彩叶酱看着桌子上的牌。 直到你拥有 2 个棋子之前,Snuke领先并交替执行以下操作。
操作:从当前桌上的牌中选择一张牌。 1 选择一个,将其拾起,并完全删除其存在。
所有操作完成后仍然存在 本游戏的得分是 2 卡片上写的整数之差的绝对值。
这个游戏对于第一步和第二步都有附加规则。
- Snuke,第一个玩家,在轮到他时必须始终选择放在中间的牌。换句话说,此时剩余的牌数。 从左开始,如 r 作为一张纸,从左边开始 (r+1)/2 卡的存在必须被删除。
- 正在抽签的彩羽酱在轮到她时必须选择剩余卡牌中最左边的卡牌或最右边的卡牌。
求当 Iroha-chan 采取最佳行动以使本场比赛的得分最小化时,本场比赛的得分是多少。
制約
- 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按行输出。
入力例1
3 1 5 100
出力例1
99
从左边潜袭 第 2 张牌被删除,游戏结束。
入力例2
9 3 14 15 20 33 51 59 62 68
出力例2
45
解説
解説第 3 页文本第二行中的“最大值”不正确为“最小值”。对不起。
(5/13 21:40 追記)