레이팅 미적용설명
JOI 君はN 個の碁石を持っている.それぞれの碁石には1 からN までの番号が付けられており,1 以上
109 以下の整数で表される色で塗られている.最初,碁石i (1 ≦i ≦N) の色はAi である.
JOI 君はこれからN 回の操作を行い,碁石をテーブルの上に1 列に並べたい.i 回目(1 ≦i ≦N) の操作
は以下のような手順で行われる.
1. 碁石i を碁石i −1 の右隣に置く.ただし,i = 1 の場合は,碁石1 をテーブルの上に置く.
2. 碁石1, 2, . . . , i −1 のうち現在の色が碁石i と同じであるものが存在する場合,それらのうち番号が最
も大きいものをj とすると,碁石j + 1, j + 2, . . . , i −1 の色をすべて色Ai に塗り替える.
操作を正しく行ったか確認するために,JOI 君はすべての操作を行った後の碁石の色を予め知っておき
たい.
碁石の情報が与えられたとき,N 回の操作を行った後のそれぞれの碁石の色を求めるプログラムを作成
せよ.
제약
• 1 ≦N ≦200 000.
• 1 ≦Ai ≦109 (1 ≦i ≦N).
• 入力される値はすべて整数である.
- (25 点) N ≦2 000.
- (35 点) Ai ≦2 (1 ≦i ≦N).
- (40 点) 追加の制約はない.
입력 형식
入力は以下の形式で標準入力から与えられる.
N
A1
A2
...
AN
출력 형식
標準出力にN 行で出力せよ.i 行目(1 ≦i ≦N) には,N 回の操作を行った後の碁石i の色を出力せよ.
第22 回日本情報オリンピック(JOI 2022/2023) 本選
2023 年2 月12 日(オンライン開催)
예제 1
입력
6
1
2
1
2
3
2
출력
1
1
1
2
2
2
예제 2
입력
10
1
1
2
2
1
2
2
1
1
2
출력
1
1
1
1
1
1
1
1
1
2
문제 정보