D - Strange Balls 解説 /

実行時間制限: 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