Срочные новости из неврологии зомби! Оказывается — в отличие от того как считалось ранее — что каждый зомби рождён с одним мозгом, и только потом мозг развивается в сложную структуру. На деле, каждый раз когда зомби съедает один мозг, новый мозг появляется в его нервной систему и сразу соединяется с одним из уже существующих мозгов единственной мозговой связью. Исследователи хотели бы отслеживать мозговую задержку после каждого такого изменения. Вам поставлена задача написать программу, которая по истории эволюции нервной системы конкретного зомби вычислит мозговую задержку на каждом шаге.
В первой строке входных данных записано число n — количество мозгов в финальной версии нервной системы зомби (2 ≤ n ≤ 200 000). Во второй строке дана история развития нервной системы зомби. Для удобства, мы пронумеруем мозги 1, 2, ... n в порядке их добавления в нервную систему (зомби рождается с единственным мозгом с номером 1, а добавляются мозги 2, 3, ... n). Во второй строке записано n - 1 целое число p2, p3, ..., pn, означающее что после добавления мозга с номером k в нервную систему, он был соединён с родительским мозгом 
.
Выведите n - 1 число — мозговую задержку после добавления мозга с номером k для k = 2, 3, ..., n.
6
1
2
2
1
5
1 2 2 3 4
