Условие

Компания состоит из $n$ сотрудников с идентификаторами $1, 2, \dots, n$. Сотрудник $1$ — босс, а у каждого другого сотрудника $i$ ($2 \le i \le n$) есть непосредственный руководитель $f_i$ ($1 \le f_i < i$). Структура компании образует корневое дерево с корнем в вершине $1$.

В этой компании сотрудник $a$ знает сотрудника $b$ тогда и только тогда, когда выполняется хотя бы одно из следующих условий:

• $a = b$.
• $b$ является предком $a$. Иными словами, существует последовательность $u_1, u_2, \dots, u_k$ ($2 \le k$) такая, что $u_1 = a$, $u_k = b$ и $u_i = f_{u_{i-1}}$ для всех $2 \le i \le k$.
• $b$ является непосредственным сыном $a$ ($b$ — непосредственный подчинённый $a$). Иными словами, $f_b = a$.

Обратите внимание, что отношение знакомства не обязательно симметрично: из того, что $a$ знает $b$, не следует, что $b$ знает $a$.

Сейчас сотрудники играют в игру. В каждом раунде некоторый сотрудник $m$ выступает в роли отгадывающего, а другой сотрудник $p$ является целью. Гарантируется, что $p$ — это сотрудник, которого $m$ не знает.

Чтобы определить $p$, $m$ задаёт последовательность вопросов. В каждом вопросе $m$ выбирает некоторый ID $x$ и спрашивает: «Знает ли $p$ сотрудника $x$?» Сотрудник $p$ всегда отвечает правдиво. Кроме того, если $x = p$, то $p$ специально сообщает, что он и есть сотрудник $x$, после чего игра немедленно заканчивается.

Каждый вопрос имеет стоимость перемещения по дереву компании. Если $i$-й вопрос касается сотрудника $x_i$, то стоимость этого вопроса равна $dis(x_{i-1}, x_i)$, где $dis(a, b)$ — количество рёбер на единственном простом пути между $a$ и $b$ в дереве. Для первого вопроса ($i = 1$) стоимость равна $dis(m, x_1)$.

Сотрудник $m$ чрезвычайно умён и использует оптимальную стратегию, минимизирующую суммарную стоимость, необходимую для гарантированного завершения игры в худшем случае. Ваша задача — вычислить эту минимальную стоимость в худшем случае для каждого возможного отгадывающего $m \in \{1, 2, \dots, n\}$.

Если сотрудник $m$ уже знает всех в компании, ответ для такого $m$ равен $0$.

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

Первая строка входных данных содержит целое число $n$ ($1 \le n \le 10^5$) — общее количество сотрудников в компании.

Вторая строка содержит $n - 1$ целых чисел, представляющих $f_2, f_3, \dots, f_n$. Выполняется условие $1 \le f_i < i$.

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

Выведите одну строку, содержащую $n$ целых чисел через пробел — ответы для случаев $m = 1, m = 2, \dots, m = n$.

Примеры

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

3
1 1

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

0 2 2

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

5
1 1 3 2

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

4 3 3 4 4

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

6
1 1 2 2 3

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

4 3 5 4 4 6

Примечание

Поясним случай $m = 4$ в примере 3: во-первых, как показано на рисунке, сотрудник $m$ не знает сотрудников $\{3, 5, 6\}$. Одна из возможных оптимальных стратегий — сначала спросить, знает ли $p$ сотрудника $2$, заплатив $1$. Если да, то это означает, что $p = 5$, и следующим шагом нужно спросить про сотрудника $5$, чтобы завершить игру с общей стоимостью $2$. В противном случае продолжаем и спрашиваем, знает ли $p$ сотрудника $3$, что стоит $2$. Если $p = 3$, игра заканчивается с общей стоимостью $3$. Иначе это означает, что $p = 6$, и следующий шаг стоит $1$, чтобы спросить про сотрудника $6$, завершая игру с общей стоимостью $4$. Таким образом, эта стратегия требует стоимости $4$ в худшем случае. Можно доказать, что никакая другая стратегия не может ещё сильнее уменьшить стоимость запросов в худшем случае.