102403: [AtCoder]ABC240 D - Strange Balls
Description
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
Input
题意翻译
### 【题目描述】 高桥君收到了 $N$ 个奇怪的球，球摆成一列，每个球的表面都写着一个数字，第 $i$ 个球的表面数字是 $a_i$。 高桥君准备将所有的球从 $1$ 到 $N$ 依次放入桶中。桶是圆柱形的，底面是封死的，只能从圆柱形顶端放入。桶比较窄，桶中的球只能全部竖着叠放。 高桥君在放球的过程中，奇怪的事情发生了，如果桶中有连续 $x$ 个值为 $x$ 的球，这些球将会消失。 请你帮助高桥君计算出，从 $1$ 到 $N$ 依次放入每个球后，桶中的球有多少个？ ### 【输入描述】 第一行一个正整数 $N$； 第二行 $N$ 个正整数，从 $1$ 到 $N$ 依次表示每个球表面的数字。 ### 【输出描述】 输出 $N$ 行，每行一个整数，第 $i$ 行表示放完第 $i$ 个球后桶中球的个数。 ### 【数据范围】 - $1 \le N \le 2 \times 10 ^ 5$。 - $2 \le a_i \le 2 \times 10 ^ 5$（$1 \le i \le N$）。 - 输入均为整数。Output
问题描述
高桥君有N个球。每个球上都写有一个不小于2的整数。他将一个接一个地将它们插入一个圆柱体中。第i个球上写的数是$a_i$。
这些球是由特殊材料制成的。当$k$个写有$k$（$k \geq 2$）的球排成一行时，这$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的球消失，圆柱体最终包含$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