碁石ならべ 2 (Stone Arranging 2)

Unrated

日本語

Language

Time limit: 2000 ms
Memory limit: 1024 MB
Submissions: 0
Correct: 0
Solved by: 0
AC rate: —

Statement

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

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

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

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

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

Input

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

\(N\)
\(A_1\)
\(A_2\)
\(\vdots\)
\(A_N\)

Output

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

Constraints

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

Subtasks

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

Examples

Sample input 1

Sample output 1

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

操作	並べられた碁石の色	説明
\(1\)	\(1\)	碁石 \(1\) がテーブルの上に置かれる．
\(2\)	\(1,2\)	碁石 \(2\) が碁石 \(1\) の右隣に置かれる．
\(3\)	\(1,2,1\)	碁石 \(3\) が碁石 \(2\) の右隣に置かれる．
\(3\)	\(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\) の右隣に置かれる．
\(6\)	\(1,1,1,2,2,2\)	碁石 \(5\) の色を \(2\) に塗り替える．

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

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

Sample input 2

Sample output 2

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

Notes

JOI 2023 · JCIOI · CC BY-SA 4.0