Ameba

题目描述

你观察了变形虫并记录了一些信息。 最初，有一个编号为 $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 \leq N \leq 2\times 10^5$ 记录是自洽的。即： $1\leq A_i \leq 2i-1$。 $A_i$ 互不相同。从变形虫 $1$ 出生了变形虫 $2$ 和 $3$。从变形虫 $2$ 出生了变形虫 $4$ 和 $5$。

变形虫 $1$ 与变形虫 $1$ 的代数距离为零。 变形虫 $2$ 与变形虫 $1$ 的代数距离为一代。 变形虫 $3$ 与变形虫 $1$ 的代数距离为一代。 变形虫 $4$ 与变形虫 $2$ 的代数距离为一代，与变形虫 $1$ 的代数距离为两代。 变形虫 $5$ 与变形虫 $2$ 的代数距离为一代，与变形虫 $1$ 的代数距离为两代。

标签: AtCoder|abc274C

来源

AtCoder|abc274C