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

Вы — программист, и у вас есть новогоднее дерево (нет, не елка) — дерево из четырех вершин: одна вершина степени три (имеет номер 1), связанная с тремя листами (имеют номера от 2 до 4).

На новый год программисты обычно веселятся, вот и вы решили повеселиться, добавляя вершины в свое дерево. При этом одна операция добавления выглядит следующим образом:

  • Сначала выбирается некоторой лист дерева с номером v.
  • Обозначим количество вершин в дереве на данный момент переменной n, тогда в дерево добавляются две вершины с номерами n + 1 и n + 2, а также ребро между вершинами v и n + 1 и ребро между вершинами v и n + 2.

Как и полагается, ваша задача не просто промоделировать процесс добавления вершин в дерево, но и после каждой операции добавления выводить диаметр текущего дерева. Вперед, на решение новогодней задачи!

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

В первой строке записано целое число q (1 ≤ q ≤ 5·105) — количество операций. В каждой из следующих q строк записано целое число vi (1 ≤ vi ≤ n) — операция добавления листов к вершине vi. Переменная n обозначает количество вершин в текущем дереве.

Гарантируется, что все заданные операции корректны.

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

Выведите q целых чисел — диаметр текущего дерева после каждой операции.

Примеры
Входные данные
5
2
3
4
8
5
Выходные данные
3
4
4
5
6