翻译

你是一个程序猿，现在有一棵新年树（并不是传统的带着叶子的树）——它有四个节点： 1，2，3，4. 其中2，3，4的父亲都是1.

新年里，程序猿们往往会做一些有趣的事情。你则选择以往这棵树上加节点来取乐。 一个添加节点的操作是这样的：

1） 找到树上的一个叶子结点v 2） 设现在树上有n个节点，那么你现在会加入两个节点n+1和n+2，它们都会成为n+2.

你的任务是在做q次这样的操作，并在每做完一次后计算一次树的直径。来吧，我们一起来解决这道新年问题吧！

输入：

第一行一个整数q$(1 ≤ q ≤ 5×10^5)$,表示操作次数。接下来q行，每行一个数v，表示你当前操作的节点。保证它一定是一个叶子结点。

输出：

q行，每行一个数，表示做了这个操作以后树的直径。