阿米巴

题目描述

你观察了阿米巴,并做了记录。

初始时有 $1$ 只阿米巴,编号为 $1$。

你一共做了 $N$ 条记录。根据第 $i$ 条记录,编号为 $A_i$ 的阿米巴分裂成两只新的阿米巴,它们被分别编号为 $2i$ 和 $2i+1$。

此时,称阿米巴 $A_i$ 是阿米巴 $2i$ 和 $2i+1$ 的亲代。

对于每个 $k=1,\ldots,2N+1$,阿米巴 $k$ 距离阿米巴 $1$ 隔了多少代?

输入格式

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

$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$ 与阿米巴 $1$ 相隔 $0$ 代。

阿米巴 $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

数据范围

• $1 \le N \le 2\times 10^5$
• 记录是自洽的,即:
  • $1 \le A_i \le 2i-1$
  • $A_i$ 两两不同