E. Никита и игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Никита играет в новую компьютерную игру. Всего в игре m уровней. На каждом уровне появляется новый класс, который наследуется от класса yi (и yi является родителем нового класса). Таким образом, классы образуют дерево. Изначально существует только один класс с номером 1.

Поменять класс на его соседа в дереве стоит 1 монету, причем обратно класс поменять нельзя. Стоимость смены класса a на класс b равна суммарной стоимости изменений классов на пути от a до b в дереве классов.

Пусть на i-м уровне максимальная стоимость смены одного класса на другой равна x. Выведите для каждого уровня количество классов, для которых существует такой класс y, что смена с этого класса на y стоит x.

Входные данные

Первая строке содержит целое число m — количество запросов(1 ≤ m ≤ 3·105).

Следующие m строк содержат описание уровней. Строка с номером i (1 ≤ i ≤ m) описывает i -ый уровень и содержит одно целое число yi  — номер класса, от которого наследуется класс с номером i + 1 (1 ≤ yi ≤ i) .

Выходные данные

Пусть на i -ом уровне максимальная стоимость смены одного класса на другой равна x. Выведите для каждого уровня количество классов, для которых существует такой класс y, что смена с этого класса на y стоит x.

Примеры
Входные данные
4
1
1
2
1
Выходные данные
2
2
2
3
Входные данные
4
1
1
2
3
Выходные данные
2
2
2
2