AT_iroha2019_day3_f 闇のカードゲーム

[problemUrl]: https://atcoder.jp/contests/iroha2019-day3/tasks/iroha2019_day3_f テーブルの上に、 $ N $ 枚のカードが横一列に並べられています(ただし、 $ N $ は奇数)。それぞれのカードには正の整数が $ 1 $ つずつ書かれており、左から $ i $ 番目 $ (1\ \leq\ i\ \leq\ N) $ のカードに書かれている整数は $ a_i $ です。異なるカードに同じ整数が書かれていることはありません。また、カードは、書かれている整数の小さい順に左から並べられています。 すぬけ君といろはちゃんは、テーブルに置かれているカードが $ 2 $ 枚になるまで、すぬけ君を先手として次の操作を交互に行います。 **操作**: その時点でテーブルに置かれているカードの中からカードを $ 1 $ 枚選んで手に取り、その存在を完全に消去する。 操作が全て終了したとき、まだ存在している $ 2 $ 枚のカードに書かれている整数の差の絶対値を、このゲームのスコアとします。 このゲームには先手・後手ともに追加規則が存在します。 - 先手のすぬけ君は、常に、手番が回ってきた時点で真ん中に置かれているカードを選ばなければなりません。つまり、その時点で残っているカードの枚数を $ r $ 枚として、左から $ (r+1)/2 $ 番目のカードの存在を抹消しなければなりません。 - 後手のいろはちゃんは、手番が回ってきた時点で残っているカードのうち、最も左にあるものか、最も右にあるものを選ばなければなりません。 いろはちゃんが、このゲームのスコアを最小化するように最適に行動するとき、このゲームのスコアがいくつになるかを求めなさい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1\ a_2\ \cdots\ a_N $

ゲームのスコアを$ 1 $行で出力せよ。

### 制約 - $ 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 $ ### 解説 [解説](https://img.atcoder.jp/iroha2019-day3/editorial-F.pdf) 3ページ目の本文2行目の「最大値」は「最小値」の誤りです。申し訳ございません。 (5/13 21:40 追記) ### Sample Explanation 1 すぬけ君が、左から $ 2 $ 番目のカードを消して、ゲームが終了します。