← 返回题目列表

AtCoder · abc274_c

F. 阿米巴

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

分数: 300 点

问题陈述

您观察了阿米巴原虫并保存了一些记录。

最初,有一种阿米巴原虫,编号为 1.

你做了 N 记录。根据 i第条记录,阿米巴编号 A_i 因分裂成两个新的变形虫而消失,然后对其进行编号 2i 和 2i+1.
在这里,阿米巴原虫 A_i 据说是阿米巴原虫的亲本 2i 和 2i+1.

对于每个 k=1,\ldots,2N+1,阿米巴原虫还有多少代 k 来自阿米巴 1?

约束

  • 1 \leq N \leq 2\times 10^5
  • 记录一致。即:
    • 1\leq A_i \leq 2i-1.
    • A_i 是不同的整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印 2N+1 行。的 k第行应包含变形虫之间的生成距离 1 和阿米巴原虫 k.


示例输入 1

2
1 2

示例输出 1

0
1
1
2
2

来自阿米巴 1,阿米巴原虫 2 和 3 诞生了。来自阿米巴原虫 2,阿米巴原虫 4 和 5 诞生了。

  • 阿米巴原虫 1 距离阿米巴原虫零代 1.
  • 阿米巴原虫 2 距离阿米巴仅一代 1.
  • 阿米巴原虫 3 距离阿米巴仅一代 1.
  • 阿米巴原虫 4 距离阿米巴仅一代 2,距离变形虫还有两代人 1.
  • 阿米巴原虫 5 距离阿米巴仅一代 2,距离变形虫还有两代人 1.

示例输入 2

4
1 3 5 2

示例输出 2

0
1
1
2
2
3
3
2
2