Умова

Компанія складається з $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$ у найгіршому випадку. Можна довести, що жодна інша стратегія не може ще більше зменшити вартість запитів у найгіршому випадку.