Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Вы — программист, и у вас есть новогоднее дерево (нет, не елка) — дерево из четырех вершин: одна вершина степени три (имеет номер 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 целых чисел — диаметр текущего дерева после каждой операции.