分数: 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