CF379F.New Year Tree

You are a programmer and you have a New Year Tree (not the traditional fur tree, though) — a tree of four vertices: one vertex of degree three (has number 1), connected with three leaves (their numbers are from 2 to 4).

On the New Year, programmers usually have fun. You decided to have fun as well by adding vertices to the tree. One adding operation looks as follows:

• First we choose some leaf of the tree with number v.
• Let's mark the number of vertices on the tree at this moment by variable n, then two vertexes are added to the tree, their numbers are n + 1 and n + 2, also you get new edges, one between vertices v and n + 1 and one between vertices v and n + 2.

Your task is not just to model the process of adding vertices to the tree, but after each adding operation print the diameter of the current tree. Come on, let's solve the New Year problem!

你是一名程序员，拥有一棵“新年树”（虽然它并非传统的松树）——一棵包含四个顶点的树：其中一个顶点度数为三（编号为 1），与三个叶子节点相连（编号分别为 2、3、4）。

在新年期间，程序员们通常会玩得开心。你也决定通过向这棵树中添加顶点来获得乐趣。每次添加操作如下：

• 首先选择当前树中的某个叶子节点，其编号为 $v$；
• 设此时树中已有 $n$ 个顶点，则向树中新增两个顶点，编号分别为 $n+1$ 和 $n+2$；同时新增两条边：一条连接顶点 $v$ 与 $n+1$，另一条连接顶点 $v$ 与 $n+2$。

你的任务不仅是要模拟向树中添加顶点的过程，而且每次添加操作后，都要输出当前树的直径。来吧，一起解决这个新年问题！

The first line contains integer q (1 ≤ q ≤ 5·105) — the number of operations. Each of the next q lines contains integer v__i (1 ≤ v__i ≤ n) — the operation of adding leaves to vertex v__i. Variable n represents the number of vertices in the current tree.

It is guaranteed that all given operations are correct.

第一行包含一个整数 $q$（$1 \le q \le 5 \cdot 10^5$）—— 操作的次数。接下来的 $q$ 行中，每行包含一个整数 $v_i$（$1 \le v_i \le n$）—— 表示向顶点 $v_i$ 添加叶子节点的操作。变量 $n$ 表示当前树中的顶点数量。

保证所有给定的操作均合法。

Print q integers — the diameter of the current tree after each operation.

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