問題文

テーブルの上に、 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)

入力例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 追記)