Nikita 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*.

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*).

提交代码