문제

JOI 君は $N$ 個の碁石を持っている．それぞれの碁石には $1$ から $N$ までの番号が付けられており，$1$ 以上 $10^9$ 以下の整数で表される色で塗られている．最初，碁石 $i$ ($1 \le i \le N$) の色は $A_i$ である．

JOI 君はこれから $N$ 回の操作を行い，碁石をテーブルの上に $1$ 列に並べたい．$i$ 回目 ($1 \le i \le N$) の操作は以下のような手順で行われる．

1. 碁石 $i$ を碁石 $i-1$ の右隣に置く．ただし，$i = 1$ の場合は，碁石 $1$ をテーブルの上に置く．
2. 碁石 $1, 2, \ldots, i-1$ のうち現在の色が碁石 $i$ と同じであるものが存在する場合，それらのうち番号が最も大きいものを $j$ とすると，碁石 $j+1, j+2, \ldots, i-1$ の色をすべて色 $A_i$ に塗り替える．

操作を正しく行ったか確認するために，JOI 君はすべての操作を行った後の碁石の色を予め知っておきたい．

碁石の情報が与えられたとき，$N$ 回の操作を行った後のそれぞれの碁石の色を求めるプログラムを作成せよ．

입력

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

N
A_1
A_2
...
A_N

출력

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

예제 입력 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

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

제한

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

서브태스크

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