题目描述

你观察了变形虫并记录了一些数据。最初，只有一个编号为$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

4
1 3 5 2

0
1
1
2
2
3
3
2
2

样例1解释

从变形虫1，诞生了变形虫2和3。从变形虫2，诞生了变形虫4和5。

• 变形虫1与变形虫1相隔零代。
• 变形虫2与变形虫1相隔一代。
• 变形虫3与变形虫1相隔一代。
• 变形虫4与变形虫2相隔一代，与变形虫1相隔两代。
• 变形虫5与变形虫2相隔一代，与变形虫1相隔两代。

数据范围

$1 \leq N \leq 2\times 10^5$，记录是一致的。
也就是说： $1\leq A_i \leq 2i-1$，$A_i$是不同的整数。

来源

• AtCoder ABC274C