Score : $400$ points

问题描述

Takahashi 有 $N$ 个球。每个球上都写着一个不小于 $2$ 的整数。他将逐个将它们放入一个圆柱体中。第 $i$ 个球上写的整数是 $a_i$。

这些球是由特殊材料制成的。当有 $k$ 个写有数字 $k$ $(k \geq 2)$ 的球排成一排时，这 $k$ 个球都会消失。

对于每个 $i$ $(1 \leq i \leq N)$，计算插入第 $i$ 个球后剩余的球的数量。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:20:52