当前没有测试数据。

C - Ameba

分数：300分

问题描述

你观察到了变形虫，并记录了一些信息。

初始时，只有一个编号为1的变形虫。

你做了N个记录。根据第i条记录，编号为Ai的变形虫通过分裂生成了两个新的变形虫，它们的编号分别为2i和2i+1。
也就是说，变形虫Ai是变形虫2i和2i+1的父母。

对于每个k=1,2,...,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的代数距离。

2
1 2

0
1
1
2
2

从变形虫1开始，变形虫2和变形虫3分裂而生。从变形虫2开始，变形虫4和变形虫5分裂而生。

• 变形虫1距离自己没有代数距离。
• 变形虫2距离变形虫1有1代的代数距离。
• 变形虫3距离变形虫1有1代的代数距离。
• 变形虫4距离变形虫2有1代的代数距离，距离变形虫1有2代的代数距离。
• 变形虫5距离变形虫2有1代的代数距离，距离变形虫1有2代的代数距离。

4
1 3 5 2

0
1
1
2
2
3
3
2
2