← 返回题目列表

AtCoder · abc240_d

G. 奇怪的球

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

高桥有 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-st 球,圆柱体包含带有 3.
  • 插入后 2-nd 球,气缸包含 3, 2 从下到上。
  • 插入后 3-rd 球,圆柱体包含 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