実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
高橋君は 2 以上の整数が書かれた N 個のボールを持っており、これらを細長い筒の中に落としていきます。i \, (1 \leq i \leq N) 回目には、a_i が書かれたボールを落とします。
ボールは特殊な材質でできており、筒の中において k \, (k \geq 2) が書かれたボールが k 個連続すると、それら k 個のボールは全て消えてしまいます。
各 i \, (1 \leq i \leq N) について、i 個目のボールを筒の中に落とした後、筒の中に何個のボールがあるか求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 2 \leq a_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
N 行出力せよ。i \, (1 \leq i \leq N) 行目には、i 個目のボールを筒の中に落とした後、筒の中にあるボールの個数を出力せよ。
入力例 1
5 3 2 3 2 2
出力例 1
1 2 3 4 3
筒の中は次のように変化します。
- 1 個目のボールを落とす。筒の中にあるボールに書かれた整数は 3 である。
- 2 個目のボールを落とす。筒の中にあるボールに書かれた整数は下から順に 3, 2 である。
- 3 個目のボールを落とす。筒の中にあるボールに書かれた整数は下から順に 3, 2, 3 である。
- 4 個目のボールを落とす。筒の中にあるボールに書かれた整数は下から順に 3, 2, 3, 2 である。
- 5 個目のボールを落とす。筒の中にあるボールに書かれた整数は下から順に 3, 2, 3, 2, 2 となるが、2 が書かれたボールが 2 個連続しているのでこれらは消え、下から順に 3, 2, 3 となる。
入力例 2
10 2 3 2 3 3 3 2 3 3 2
出力例 2
1 2 3 4 5 3 2 3 1 0
Score : 400 points
Problem Statement
Takahashi has N balls. Each ball has an integer not less than 2 written on it. He will insert them in a cylinder one by one. The integer written on the i-th ball is a_i.
The balls are made of special material. When k balls with k (k \geq 2) written on them line up in a row, all these k balls will disappear.
For each i (1 \leq i \leq N), find the number of balls after inserting the i-th ball.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 2 \leq a_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
Print N lines. The i-th line (1 \leq i \leq N) should contain the number of balls after inserting the i-th ball.
Sample Input 1
5 3 2 3 2 2
Sample Output 1
1 2 3 4 3
The content of the cylinder changes as follows.
- After inserting the 1-st ball, the cylinder contains the ball with 3.
- After inserting the 2-nd ball, the cylinder contains 3, 2 from bottom to top.
- After inserting the 3-rd ball, the cylinder contains 3, 2, 3 from bottom to top.
- After inserting the 4-th ball, the cylinder contains 3, 2, 3, 2 from bottom to top.
- After inserting the 5-th ball, the cylinder momentarily has 3, 2, 3, 2, 2 from bottom to top. The two consecutive balls with 2 disappear, and the cylinder eventually contains 3, 2, 3 from bottom to top.
Sample Input 2
10 2 3 2 3 3 3 2 3 3 2
Sample Output 2
1 2 3 4 5 3 2 3 1 0