Statement : F. Game on Growing Tree

Consider a game for two players: Alice and Bob. They have a tree $T$; initially, every vertex of this tree is white. Alice and Bob take turns: Alice goes first, then Bob, then Alice again, then Bob again, and so on.

During Alice’s first turn, she has to choose a vertex and put a chip in it, then paint the chosen vertex red. During every turn except for the first one, Alice has to move the chip into an adjacent white vertex and paint that vertex red. If, at the start of Alice’s turn, there are no white vertices adjacent to the vertex with the chip, the game ends.

During each of Bob’s turns, he has to choose a white vertex and paint it blue. If there are no white vertices in the tree at the start of Bob’s turn, the game ends.

The final score of the game is the number of red vertices. Alice wants to maximize the score, Bob wants to minimize it. Both players play optimally.

This is the description of the game. The statement of the problem follows.

You are given a tree, initially consisting of only one vertex numbered $1$. Then, $q$ queries are performed; during the $i$-th query, a new vertex is added to the tree; this new vertex gets the number $(i+1)$ and is connected to the vertex $v_i$ by an edge. After each query, you have to print the final score of the game if Alice and Bob play on the current tree.

The first line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

The second line contains $q$ integers $v_1, v_2, \dots, v_q$ ($1 \le v_i \le i$), where $v_i$ is the vertex that gets connected with the vertex $(i+1)$ during the $i$-th query.

Print $q$ integers; the $i$-th of these integers should be the score if Alice and Bob play on the tree that you get after processing the $i$-th query.

Input

9
1 1 3 3 1 2 1 2 8

Output

1 2 2 2 2 2 2 3 3