AT_abc274_c [ABC274C] Ameba

你记录了对变形虫的观察。 最初有 $1$ 只变形虫，编号为 $1$。 观察记录按时间顺序共有 $N$ 条，第 $i$ 条记录为：“编号为 $A_i$ 的变形虫分裂并消失，产生了新的 $2$ 只变形虫，分别编号为 $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$ 行输出从变形虫 $k$ 向上追溯多少代父代可以追溯到变形虫 $1$。

## 限制条件 - $1 \leq N \leq 2 \times 10^5$ - 观察记录没有矛盾。即 - $1 \leq A_i \leq 2i-1$ - $A_i$ 互不相同 ## 样例解释 1 变形虫 $1$ 分裂产生了变形虫 $2,3$，变形虫 $2$ 分裂产生了变形虫 $4,5$。 - 变形虫 $1$ 追溯 $0$ 代即可到达变形虫 $1$。 - 变形虫 $2$ 追溯 $1$ 代即可到达变形虫 $1$。 - 变形虫 $3$ 追溯 $1$ 代即可到达变形虫 $1$。 - 变形虫 $4$ 追溯 $1$ 代到达变形虫 $2$，再追溯 $2$ 代到达变形虫 $1$。 - 变形虫 $5$ 追溯 $1$ 代到达变形虫 $2$，再追溯 $2$ 代到达变形虫 $1$。 由 ChatGPT 4.1 翻译