配点 : $600$ 点

問題文

長さ $2N$ の数列 $a$ が与えられます。

すぬけ君が $(1,2, \ldots, N)$ の空でない（連続するとは限らない）部分列 $x=(x_1,x_2,\ldots,x_k)$ を用いて、数列を作ろうとしています。 作られる数列は、$a$ の $x_1$ 番目、$x_2$ 番目、$\ldots$、$x_k$ 番目、$x_{1}+N$ 番目、$\ldots$、$x_{k}+N$ 番目の要素を抜き出してこの順で連結した数列です。

すぬけ君が作ることができる数列のうち、辞書順最小のものを求めてください。

制約

• 与えられる入力は全て整数
• $1 \leq N \leq 10^5$
• $1 \leq a_i \leq 10^9$

入力

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

$N$

$a_{1}$ $\cdots$ $a_{2N}$

出力

すぬけ君が作ることができる数列のうち、辞書順最小のものを出力せよ。

3
2 1 3 1 2 2

1 2

• $x = (2)$ とします。
• このとき、作られる数列は $(1,2)$ となり辞書順最小です。

10
38 38 80 62 62 67 38 78 74 52 53 77 59 83 74 63 80 61 68 55

38 38 38 52 53 77 80 55

12
52 73 49 63 55 74 35 68 22 22 74 50 71 60 52 62 65 54 70 59 65 54 60 52

22 22 50 65 54 52