[AGC006D] Median Pyramid Hard

给出一个 $N$ 层的方格金字塔,自顶向下依次标号为第 $1$ 到第 $N$ 层。 其中第 $i(1 \le i \le N)$ 层有 $2i - 1$ 个方格。（具体形态见下面的图） 第 $N$ 层有一个 $1$ 到 $2N-1$ 的排列,其他层的数字按以下规则生成：方格 $b$ 中填写的整数，是方格 $b$ 正下方、左下方和右下方方格中所写整数的中位数。 现在给出第 $N$ 层的数字，请你求第一层的数字。 翻译提供者：WAAutoMaton

[problemUrl]: https://atcoder.jp/contests/agc006/tasks/agc006_d $ N $ 段のピラミッドがあります。 段は上から順に $ 1 $, $ 2 $, $ ... $, $ N $ と番号が振られています。 各 $ 1\ <\ =i\ <\ =N $ について、$ i $ 段目には $ 2i-1 $ 個のブロックが横一列に並んでいます。 また、各段の中央のブロックに注目すると、これらは縦一列に並んでいます。 $ N=4 $ 段のピラミッド すぬけ君は $ N $ 段目のブロックに ($ 1 $, $ 2 $, $ ... $, $ 2N-1 $) を並べ替えたもの（順列）を書き込みました。 さらに、次のルールに従い、残りすべてのブロックに整数を書き込みました。 - あるブロックに書き込まれる整数は、そのブロックの左下、真下、右下のブロックに書き込まれた整数の中央値である。 ブロックに整数を書き込む例 その後、すぬけ君はすべてのブロックに書き込まれた整数を消してしまいました。 すぬけ君は、$ N $ 段目のブロックに書き込まれた順列が ($ a_1 $, $ a_2 $, $ ... $, $ a_{2N-1} $) であったことだけを覚えています。 $ 1 $ 段目のブロックに書き込まれた整数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_{2N-1} $

$ 1 $ 段目のブロックに書き込まれた整数を出力せよ。

4
1 6 3 7 4 5 2

4

2
1 2 3

2

### 制約 - $ 2\ <\ =N\ <\ =10^5 $ - ($ a_1 $, $ a_2 $, $ ... $, $ a_{2N-1} $) は ($ 1 $, $ 2 $, $ ... $, $ 2N-1 $) の順列である。 ### Sample Explanation 1 問題文中の図の例です。