Busy Beaver と Busy Revaeb の世紀にわたるライバル関係は、今日まで続いています。今回、彼らは二人対戦ゲームで互いに挑戦することにしました。

$N$ 個の正の整数からなる数列 $a_1, \dots, a_N$ があります。Busy Beaver と Busy Revaeb は、以下のようなターン制のゲームを行います。

• Busy Beaver は数列内の隣接する2つの数を選び、それらを消去して、消去した2つの数のうち大きい方を書き戻します。
• Busy Revaeb は同様のことを行いますが、消去した2つの数のうち小さい方を書き戻します。

Busy Beaver が先攻です。数列に1つの数 $X$ だけが残った時点でゲームは終了します。Busy Beaver は $X$ を最大化したいと考え、Busy Revaeb は $X$ を最小化したいと考えています。両者が最適にプレイした場合の $X$ の値を求めてください。

入力

1行目には、配列の要素数 $N$ ($1 \leq N \leq 2 \cdot 10^5$) が与えられます。

2行目には、$N$ 個の整数 $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$) が空白区切りで与えられます。

出力

両者が最適にプレイした場合に、配列に最後に残る唯一の要素の値を1つの整数で出力してください。

Scoring

• ($15$ 点) $N \leq 3$。
• ($25$ 点) $1 \leq a_i \leq 2$。
• ($60$ 点) 追加の制約なし。

入出力例

入力 1

3
2 1 4

出力 1

2

注記 1

最後の値が $4$ になることはありません。なぜなら、Busy Beaver が最初のラウンドで $4$ を選ばないことで $4$ を残そうとしても、Busy Revaeb が次のラウンドで $4$ を取ることができ、最後の値が $1$ または $2$ になるからです。また、最後の値が $1$ になることもありません。なぜなら、Busy Revaeb がラウンド1で $1$ を取ることができ、最後の値が $1$ より大きくなることを保証できるからです。

Busy Beaver は最後の値を少なくとも $2$ にすることを保証でき、Busy Revaeb は最後の値を最大でも $2$ にすることを保証できます。したがって、最適にプレイした場合、最後の値は $2$ となります。

入力 2

4
1 1 1 2

出力 2

1

注記 2

最後の値は $1$ または $2$ です。もし Busy Revaeb の戦略が $2$ を可能な限り早く取ることであるならば、Busy Beaver がターン1でどのように動こうとも、自分のターン（ターン2）終了後に数列が $1$ だけになることを保証できます。したがって、両者が最適にプレイした場合、最後の値は $1$ となります。