D. Адам и дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Когда у Адама появляется корневое дерево (связный неориентированный граф без циклов), он сразу начинает его раскрашивать. Более формально, каждому ребру он сопоставляет некоторый цвет таким образом, чтобы выполнялись два условия:

  • Не существует вершины, у которой больше двух инцидентных ребер покрашены в один цвет.
  • Для любых двух вершин, у которых есть инцидентные ребра, покрашенные в один цвет (скажем, c), путь между ними содержит ребра только цвета c.

Не все раскраски дерева нравятся Адаму одинаково. Рассмотрим путь от некоторой вершины до корня. Количество различных цветов на этом пути назовем стоимостью вершины. Стоимостью раскраски дерева будем называть максимальную стоимость среди всех вершин дерева. Помогите Адаму определить минимальную стоимость раскраски дерева.

Изначально дерево Адама состоит из одной вершины, которая имеет номер один и является корнем. За один ход Адам подвешивает к уже существующей вершине новую, которая получает номер, равный наименьшему положительному целому не занятому числу. После каждой операции вам нужно сообщать минимальную стоимость раскраски получившегося дерева.

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

В первой строке задано целое число n (1 ≤ n ≤ 106) — количество добавлений новых вершин. Во второй строке записано n чисел pi (1 ≤ pi ≤ i) — номера вершин, к которым подвешивают очередную вершину.

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

Выведите n целых чисел — минимальные стоимости раскраски дерева после каждого добавления.

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

На картинке изображен один из возможных вариантов раскраски дерева из примера в самый последний момент. Стоимость вершин с номерами 11 и 12 равна трем.