Ви спостерігали за амебами і вели деякі записи.

Спочатку була одна амеба під номером 1. Ви зробили \(N\) записів. Відповідно до \(i\)-го запису амеба під номером \(A_i\) зникла, розділившись на дві нові амеби, які потім були пронумеровані \(2i\) та \(2i+1\).

Амеба \(A_i\) є батьком амеб \(2i\) та \(2i+1\).

Для кожного \(k=1,\ldots,2N+1\), скільки поколінь віддаляє амебу \(k\) від амеби 1?

Обмеження

• \(1 \leq N \leq 2 \times 10^5\)
• Записи послідовні. Це:
• \(1\leq A_i \leq 2i-1\).
• \(A_i\) є різними цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(N\)

Наступний  рядок містить \(N\) цілих чисел \(A_i\)

Числа розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть \(2N+1\) рядків. \(K\)-й рядок має містити відстань покоління між амебою 1 та амебою \(k\).

Приклад вхідних даних

2
1 2

Приклад вихідних даних

0
1
1
2
2

Від амеби 1 народилися амеби 2 і 3. Від амеби 2 народилися амеби 4 і 5.

• Амеба 1 знаходиться в нульовому поколінні від амеби 1.
• Амеба 2 є на одне покоління від амеби 1.
• Амеба 3 є на одне покоління від амеби 1.
• Амеба 4 знаходиться на відстані одного покоління від амеби 2 і двох поколінь від амеби 1.
• Амеба 5 знаходиться на відстані одного покоління від амеби 2 і двох поколінь від амеби 1.

Приклад вхідних даних

4
1 3 5 2

Приклад вихідних даних

0
1
1
2
2
3
3
2
2