← 返回题目列表

Codeforces · 379/F

F. 新年树

中文机器翻译题面 查看原题

你是一名程序员,你有一棵新年树(不过不是传统的毛皮树)——一棵有四个顶点的树:一个三阶顶点(编号为 1),与三片叶子相连(编号从 2 到 4)。

过年的时候,程序员们通常都玩得很开心。您决定通过向树添加顶点来获得乐趣。一种添加操作如下所示:

- 首先我们选择树上编号为 v 的一些叶子。
- 让我们用变量n来标记此时树上的顶点数,然后将两个顶点添加到树中,它们的编号是n + 1和n + 2,同时你会得到新的边,一条在顶点v和n + 1之间,一条在顶点v和n + 2之间。

您的任务不仅仅是对向树添加顶点的过程进行建模,而是在每次添加操作后打印当前树的直径。来吧,我们来解决新年问题吧!

输入

第一行包含整数 q (1 ≤ q ≤ 5·105) — 操作数。接下来的 q 行中的每一行都包含整数 vi (1 ≤ vi ≤ n) — 将叶子添加到顶点 vi 的操作。变量n表示当前树中的顶点数。

保证所有给定的操作都是正确的。

输出

打印 q 个整数 — 每次操作后当前树的直径。

示例

输入 #1

5
2
3
4
8
5

输出 #1

3
4
4
5
6