U312903 鲁滨逊漂流记

《鲁滨逊漂流记》只讲到了鲁滨逊在岛上建立起一个自给自足的生态环境。 而大家不知道的是，在此之后，鲁滨逊因为太无聊，开始探索周边的岛屿，一共 $N$ 天。 鲁滨逊第 $1$ 天在岛 $1$ 上，第 $i$ 天发现了岛 $i$，并建立了一条岛 $i$ 到岛 $X_i$ 的航线，长度为 $1$（保证 $X_i < i$）。 现在鲁滨逊想知道，在第 $i$ 天他的“疆土”有多大，也就是已发现的 $2$ 个岛屿之间的最大距离（沿着航道走的简单路径长度）。 栈空间请注意！

第一行，$1$ 个整数 $N$。 接下来 $N-1$ 行，第 $i$ 行 $1$ 个整数 $X_i$，表示从岛 $i$ 到岛 $X_i$ 的航道。

输出共 $N-1$ 行，第 $i$ 行表示第 $i+1$ 天时，岛与岛之间的最大距离。

对于 $30\%$ 的数据，有 $2 \le N \le 10^3$。 对于 $100\%$ 的数据，有 $2 \le N \le 2*10^5$。