AT_arc165_f [ARC165F] Make Adjacent

[problemUrl]: https://atcoder.jp/contests/arc165/tasks/arc165_f 長さ $ 2n $ の整数列 $ X=(X_1,X_2,\dots,X_{2n}) $ のうち、すべての $ i=1,2,\dots,n $ に対し $ X_{2i-1}=X_{2i} $ が成り立つものを **良い数列** と呼びます。 長さ $ 2N $ の整数列 $ A=(A_1,A_2,\dots,A_{2N}) $ があります。この整数列は各整数 $ i=1,2,\dots,N $ をちょうど $ 2 $ 個ずつ含みます。 $ A $ に対して「隣接する $ 2 $ 項の値を入れ替える」という操作を $ 0 $ 回以上行うことで、 $ A $ を **良い数列** にしたいです。 $ A $ を **良い数列** にするのに必要な最小の操作回数を $ K $ としたとき、 $ A $ に対し操作を $ K $ 回行うことで得られる **良い数列** のうち、辞書式順序で最小のものを求めてください。 数列の辞書順とは？数列 $ S\ =\ (S_1,S_2,\ldots,S_{|S|}) $ が数列 $ T\ =\ (T_1,T_2,\ldots,T_{|T|}) $ より**辞書順で小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、$ |S|,\ |T| $ はそれぞれ $ S,\ T $ の長さを表します。 1. $ |S|\ \lt\ |T| $ かつ $ (S_1,S_2,\ldots,S_{|S|})\ =\ (T_1,T_2,\ldots,T_{|S|}) $。 2. ある整数 $ 1\ \leq\ i\ \leq\ \min\lbrace\ |S|,\ |T|\ \rbrace $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ (S_1,S_2,\ldots,S_{i-1})\ =\ (T_1,T_2,\ldots,T_{i-1}) $ - $ S_i $ が $ T_i $ より（数として）小さい。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_{2N} $

$ A $ に対し操作を $ K $ 回行うことで得られる **良い数列** のうち、辞書式順序で最小のものを空白区切りで出力してください。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ N $ - 各整数 $ i=1,2,\dots,N $ は $ A $ にちょうど $ 2 $ 個ずつ含まれる - 入力される値はすべて整数 ### Sample Explanation 1 例えば $ (3,2,1,2,3,1)\ \rightarrow\ (3,2,1,3,2,1)\ \rightarrow\ (3,2,3,1,2,1)\ \rightarrow\ (3,3,2,1,2,1)\ \rightarrow\ (3,3,2,2,1,1) $ というように $ 4 $ 回の操作で $ A $ を \*\*良い数列\*\* にすることができ、これが最小の操作回数です。 $ 4 $ 回の操作では他に $ A=(2,2,3,3,1,1) $ とすることもできるので、答えは $ (2,2,3,3,1,1) $ となります。