4236: Ameba

# Ameba ### 内存 128MB ### 时间 1S ## 题目描述 你观察了变形虫并记录了一些数据。最初，只有一个编号为$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$之间的代际距离。 ## 输入输出样例 ### 输入样例1 ``` 2 1 2 ``` ### 输出样例1 ``` 0 1 1 2 2 ``` ### 输入样例2 ``` 4 1 3 5 2 ``` ### 输出样例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$是不同的整数。 ## 题目来源 ABC274C