Мирко стал генеральным директором крупной корпорации. В компании работает N человек, которые пронумерованы числами от 1 до N, причем сам Мирко имеет номер 1. У всех работников, кроме Мирко, есть начальник. Начальник может иметь несколько подчиненных, но не более одного своего начальника.
Когда Мирко получает задание от инвесторов, он передает его своему подчиненному с наименьшим номером. Этот подчиненный также передает его своему подчиненному с наименьшим номером, и так далее, пока задание не перейдет несчастливому работнику без подчиненных, который должен его выполнить.
Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 монеты, и так далее. Потом тот, кто на самом деле сделал работу, осознает, насколько эта капиталистическая система несправедлива, и увольняется с работы.
Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации.
Ему стало интересно, сколько всего монет получил каждый бывший сотрудник. Помогите ему с этим.
Входные данные:
Первая строка содержит одно натуральное число N (1 ≤ N ≤ 2·10
5) — число сотрудников компании. Следующая строка содержит N-1 чисел a
2, a
3, ... a
n (1 ≤ a
i < i), a
i — номер начальника i-го сотрудника.
Выходные данные:
Выведите N чисел, i-е число должно означать, сколько монет получил i-й сотрудник.
Примеры:
| Входные Данные |
Выходные данные |
3
1 1 |
5 1 1 |
5
1 2 2 4 |
13 8 1 3 1 |
Пояснения:
Далее приведено описание ко второму примеру.
Мирко отдает первое задание работнику 2, который передает его работнику 3, который выполняет задание. Таким образом, работник 3 получает одну монету, работник 2 — две монеты, а работник 1, сам Мирко, — три монеты. После этого работник 3 увольняется.
Мирко отдает второе задание работнику 2, который передает его работнику 4, который тут же передает задание работнику 5, который выполняет задание. После этого работник 5 получает одну монету, работник 4 — две монеты, работник 2 — три монеты, а Мирко — четыре монеты. Работник 5 увольняется.
После выполнения третьего задания работник 4 получает одну монету, работник 2 — две монеты, а Мирко — три монеты, после чего работник 4 увольняется.
После выполнения четвертого задания работник 2 получает одну монету, а Мирко — две монеты, после чего второй работник увольняется.
Наконец, пятое задание выполняет сам Мирко, получая за это одну монету, после чего процесс прекращается.
Суммарно Мирко получил 13 монет, работник 2 — 8 монет, работник 4 — 3 монеты, а работники 3 и 5 — одну монету.