問題文

テーブルの上に、 $N$ 枚のカードが横一列に並べられています(ただし、 $N$ は奇数)。それぞれのカードには正の整数が $1$ つずつ書かれており、左から $i$ 番目 $(1 \\leq i \\leq N)$ のカードに書かれている整数は $a_i$ です。異なるカードに同じ整数が書かれていることはありません。また、カードは、書かれている整数の小さい順に左から並べられています。

すぬけ君といろはちゃんは、テーブルに置かれているカードが $2$ 枚になるまで、すぬけ君を先手として次の操作を交互に行います。

操作: その時点でテーブルに置かれているカードの中からカードを $1$ 枚選んで手に取り、その存在を完全に消去する。

操作が全て終了したとき、まだ存在している $2$ 枚のカードに書かれている整数の差の絶対値を、このゲームのスコアとします。

このゲームには先手・後手ともに追加規則が存在します。

• 先手のすぬけ君は、常に、手番が回ってきた時点で真ん中に置かれているカードを選ばなければなりません。つまり、その時点で残っているカードの枚数を $r$ 枚として、左から $(r+1)/2$ 番目のカードの存在を抹消しなければなりません。
• 後手のいろはちゃんは、手番が回ってきた時点で残っているカードのうち、最も左にあるものか、最も右にあるものを選ばなければなりません。

いろはちゃんが、このゲームのスコアを最小化するように最適に行動するとき、このゲームのスコアがいくつになるかを求めなさい。

制約

• $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ページ目の本文2行目の「最大値」は「最小値」の誤りです。申し訳ございません。

(5/13 21:40 追記)