問題文

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 回の操作を行った後のそれぞれの碁石の色を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (25 点) N \leqq 2\,000．
2. (35 点) A_i \leqq 2 (1 \leqq i \leqq N)．
3. (40 点) 追加の制約はない．

入力例 1

6
1
2
1
2
3
2

出力例 1

1
1
1
2
2
2

操作は以下の表のように行われる．

最終的に，碁石 1，2，3，4，5，6 の色はそれぞれ 1，1，1，2，2，2 となる．

この入力例は小課題 1, 3 の制約を満たす．

入力例 2

10
1
1
2
2
1
2
2
1
1
2

出力例 2

1
1
1
1
1
1
1
1
1
2

この入出力例はすべての小課題の制約を満たす．