Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Nikita and game

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputNikita plays a new computer game. There are *m* levels in this game. In the beginning of each level a new class appears in the game; this class is a child-class of the class *y*_{i} (and *y*_{i} is called parent-class for this new class). Thus, the classes form a tree. Initially there is only one class with index 1.

Changing the class to its neighbour (child-class or parent-class) in the tree costs 1 coin. You can not change the class back. The cost of changing the class *a* to the class *b* is equal to the total cost of class changes on the path from *a* to *b* in the class tree.

Suppose that at *i* -th level the maximum cost of changing one class to another is *x*. For each level output the number of classes such that for each of these classes there exists some other class *y*, and the distance from this class to *y* is exactly *x*.

Input

First line contains one integer number *m* — number of queries (1 ≤ *m* ≤ 3·10^{5}).

Next *m* lines contain description of queries. *i* -th line (1 ≤ *i* ≤ *m*) describes the *i* -th level and contains an integer *y*_{i} — the index of the parent-class of class with index *i* + 1 (1 ≤ *y*_{i} ≤ *i*).

Output

Suppose that at *i* -th level the maximum cost of changing one class to another is *x*. For each level output the number of classes such that for each of these classes there exists some other class *y*, and the distance from this class to *y* is exactly *x*.

Examples

Input

4

1

1

2

1

Output

2

2

2

3

Input

4

1

1

2

3

Output

2

2

2

2

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/24/2019 02:39:16 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|