Counterspells

The card game Magic: The Gathering has a rule for casting and countering spells. The coloring rule below comes from it. The card game itself is not explained here, and you do not need to know it to solve this problem.

For every rooted tree there is exactly one way to color the vertices black and white that satisfies this condition:

• A vertex is white if and only if it has a black child.

Induction proves that this coloring is unique. A tree colored this way is called well colored.

Start with a tree that consists of one black vertex, the root, and perform the following operation $n$ times:

• $add(v)$: attach a new black vertex to the tree as a child of vertex $v$. Then invert the colors of some vertices so that the tree is well colored again. You may invert none of them, and you may invert all of them.

For each operation, find how many vertices are inverted.

The root is numbered $0$, and the other vertices are numbered $1, 2, \dots, n$ in the order they are added to the tree.

The first line contains one integer $n$, the number of vertex additions. ($1 \le n \le 200000$)

Each of the next $n$ lines contains one integer $v_i$, the parent of the vertex added in the $i$-th operation. Vertex $v_i$ already exists before the $i$-th operation, so $v_i < i$.

Print $n$ lines. The $i$-th line contains the number of vertices whose color is inverted during the $i$-th operation. The vertex attached by that operation arrives black and a leaf is always black, so it is never one of the inverted vertices.

The figure below shows the starting tree of the first example and the tree after each operation. The vertices inverted by that operation have a red outline.