配点 : $1300$ 点

問題文

$N$ 段のピラミッドがあります。 段は上から順に $1$, $2$, $...$, $N$ と番号が振られています。 各 $1 \leq i \leq N$ について、$i$ 段目には $2i-1$ 個のブロックが横一列に並んでいます。 また、各段の中央のブロックに注目すると、これらは縦一列に並んでいます。

$N=4$ 段のピラミッド

すぬけ君は $N$ 段目のブロックに ($1$, $2$, $...$, $2N-1$) を並べ替えたもの（順列）を書き込みました。 さらに、次のルールに従い、残りすべてのブロックに整数を書き込みました。

• あるブロックに書き込まれる整数は、そのブロックの左下、真下、右下のブロックに書き込まれた整数の中央値である。

ブロックに整数を書き込む例

その後、すぬけ君はすべてのブロックに書き込まれた整数を消してしまいました。 すぬけ君は、$N$ 段目のブロックに書き込まれた順列が ($a_1$, $a_2$, $...$, $a_{2N-1}$) であったことだけを覚えています。

$1$ 段目のブロックに書き込まれた整数を求めてください。

制約

• $2 \leq N \leq 10^5$
• ($a_1$, $a_2$, $...$, $a_{2N-1}$) は ($1$, $2$, $...$, $2N-1$) の順列である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $a_2$ $...$ $a_{2N-1}$

出力

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

4
1 6 3 7 4 5 2

4

問題文中の図の例です。

2
1 2 3

2