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

输入 #1

2
1 2

输出 #1

0
1
1
2
2

输入输出样例 #2

输入 #2

4
1 3 5 2

输出 #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

变形虫 $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 翻译