Аркадий работает в крупной компании. Всего в компании n сотрудников, при этом действует жесткая иерархия. А именно, у каждого сотрудника, кроме директора, есть ровно один непосредственный начальник, а директор является начальником (через цепочку непосредственных подчиненных) всех сотрудников.
У каждого сотрудника есть ранг, выраженный целым числом. У директора ранг равен 1, а каждый другой сотрудник имеет ранг на 1 больший, чем ранг его непосредственного начальника.
У Аркадия неплохая позиция в компании, однако он чувствует, что он — никто в структуре компании, и есть много людей, которые могут заменить его. Он ввел понятие заменяемости. Рассмотрим сотрудника a и сотрудника b, который является начальником a (не обязательно непосредственным). Тогда заменяемостью r(a, b) сотрудника a относительно начальника b называется количество подчиненных (не обязательно непосредственных) данного начальника b, ранг которых не превосходит ранга данного подчиненного a. Кроме заменяемости, Аркадий ввел еще и понятие ничтожности. Ничтожность za сотрудника a равна сумме его заменяемостей относительно всех его начальников, то есть 
, где сумма берется по всем его начальникам b.
Аркадию интересна не только своя ничтожность, но и ничтожность всех остальных сотрудников компании. Найдите для Аркадия ничтожность каждого из сотрудников.
В первой строке находится одно целое число n (1 ≤ n ≤ 5·105) — количество сотрудников в компании.
Во второй строке находится n целых чисел p1, p2, ..., pn (0 ≤ pi ≤ n), где pi = 0, если i-й сотрудник является директором, а иначе pi равно номеру сотрудника, являющегося непосредственным начальником сотрудника номер i. Сотрудники нумеруются от 1 до n. Гарантируется, что среди этих чисел встречается ровно один 0, а также то, что директор является начальником (не обязательно непосредственным) для всех остальных сотрудников.
Выведите n целых чисел — ничтожности всех сотрудников в порядке их нумерации: z1, z2, ..., zn.
4
0 1 2 1
0 2 4 2
5
2 3 4 5 0
10 6 3 1 0
5
0 1 1 1 3
0 3 3 3 5
Рассмотрим первый пример. Тогда:
- У директора нет начальников, поэтому z1 = 0.
- r(2, 1) = 2 (сотрудники 2 и 4 подходят, сотрудник 3 имеет слишком большой ранг). Поэтому z2 = r(2, 1) = 2.
- Аналогично, z4 = r(4, 1) = 2.
- r(3, 2) = 1 (сотрудник 3 является подчиненным 2 и имеет необходимый ранг). r(3, 1) = 3 (подходят сотрудники 2, 3, 4). Поэтому z3 = r(3, 2) + r(3, 1) = 4.
