问题描述

Takahashi 有 N 个球。每个球上都有一个不小于 2 的整数 a_i。他将这些球一个接一个地插入一个圆柱体中。

这些球由特殊材料制成。当有 k 个球（k ≥ 2）上面写着相同的数字 k 时，这些球会消失。

对于每个 i（1 ≤ i ≤ N），求在插入第 i 个球后圆柱体中剩余的球的数量。

输入

输入的格式如下：

N
a_1
a_2
…
a_N

其中：

• N：球的数量。
• a_i：第 i 个球上写的数字。

输出

输出 N 行，第 i 行表示在插入第 i 个球后，圆柱体中剩余的球的数量。

限制

• 1 ≤ N ≤ 2 × 10^5
• 2 ≤ a_i ≤ 2 × 10^5 （1 ≤ i ≤ N）
• 输入中的所有值都是整数。

样例输入 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，共3个。

解题思路

• 使用栈（Stack）来模拟圆柱体的插入与消失过程。
  • 每次插入球时，检查栈顶是否存在相同的球，并检查它们的数量是否足够消失。
  • 如果存在连续相同的球，数量达到该球的值 k 时，就将这些球从栈中移除。
  • 每次插入之后，我们可以直接输出当前栈中球的数量。