AT_joi2023ho_a 碁石ならべ 2 (Stone Arranging 2)

JOI 君は $ N $ 個の碁石を持っている．それぞれの碁石には $ 1 $ から $ N $ までの番号が付けられており， $ 1 $ 以上 $ 10^9 $ 以下の整数で表される色で塗られている．最初，碁石 $ i $ ( $ 1 \leqq i \leqq N $ ) の色は $ A_i $ である． JOI 君はこれから $ N $ 回の操作を行い，碁石をテーブルの上に $ 1 $ 列に並べたい． $ i $ 回目 ( $ 1 \leqq i \leqq N $ ) の操作は以下のような手順で行われる． 1. 碁石 $ i $ を碁石 $ i-1 $ の右隣に置く．ただし， $ i=1 $ の場合は，碁石 $ 1 $ をテーブルの上に置く． 2. 碁石 $ 1, 2, \dots, i-1 $ のうち現在の色が碁石 $ i $ と同じであるものが存在する場合，それらのうち番号が最も大きいものを $ j $ とすると，碁石 $ j+1, j+2, \dots, i-1 $ の色をすべて色 $ A_i $ に塗り替える． 操作を正しく行ったか確認するために，JOI 君はすべての操作を行った後の碁石の色を予め知っておきたい． 碁石の情報が与えられたとき， $ N $ 回の操作を行った後のそれぞれの碁石の色を求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \vdots $ $ A_N $

標準出力に $ N $ 行で出力せよ． $ i $ 行目 ( $ 1 \leqq i \leqq N $ ) には， $ N $ 回の操作を行った後の碁石 $ i $ の色を出力せよ． ---

### 小課題 1. ( $ 25 $ 点) $ N \leqq 2\,000 $ ． 2. ( $ 35 $ 点) $ A_i \leqq 2 $ ( $ 1 \leqq i \leqq N $ )． 3. ( $ 40 $ 点) 追加の制約はない． --- ### Sample Explanation 1 操作は以下の表のように行われる． 操作並べられた碁石の色説明 $ 1 $ $ 1 $ 碁石 $ 1 $ がテーブルの上に置かれる． $ 2 $ $ 1,2 $ 碁石 $ 2 $ が碁石 $ 1 $ の右隣に置かれる． $ 3 $ $ 1,2,1 $ 碁石 $ 3 $ が碁石 $ 2 $ の右隣に置かれる． $ 1,1,1 $ 碁石 $ 2 $ の色を $ 1 $ に塗り替える． $ 4 $ $ 1,1,1,2 $ 碁石 $ 4 $ が碁石 $ 3 $ の右隣に置かれる． $ 5 $ $ 1,1,1,2,3 $ 碁石 $ 5 $ が碁石 $ 4 $ の右隣に置かれる． $ 6 $ $ 1,1,1,2,3,2 $ 碁石 $ 6 $ が碁石 $ 5 $ の右隣に置かれる． $ 1,1,1,2,2,2 $ 碁石 $ 5 $ の色を $ 2 $ に塗り替える．最終的に，碁石 $ 1 $ ， $ 2 $ ， $ 3 $ ， $ 4 $ ， $ 5 $ ， $ 6 $ の色はそれぞれ $ 1 $ ， $ 1 $ ， $ 1 $ ， $ 2 $ ， $ 2 $ ， $ 2 $ となる． この入力例は小課題 $ 1, 3 $ の制約を満たす． --- ### Sample Explanation 2 この入出力例はすべての小課題の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 200\,000 $ ． - $ 1 \leqq A_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - 入力される値はすべて整数である．