Problem
Mirko se tornou o CEO de uma grande corporação. A empresa emprega N pessoas, que são numeradas de 1 a N, e o próprio Mirko tem o número 1. Todos os funcionários, exceto Mirko, têm um chefe. Um chefe pode ter vários subordinados, mas não mais que um chefe.
Quando Mirko recebe uma atribuição de investidores, ele a entrega a seu subordinado com o menor número. Esse subordinado também o passa para seu subordinado de menor número, e assim por diante, até que o trabalho passe para um trabalhador infeliz sem subordinados para concluí-lo.
Aquele trabalhador recebe 1 moeda, seu chefe recebe 2 moedas, o chefe daquele chefe recebe 3 moedas e assim por diante. Então aquele que realmente fez o trabalho percebe o quão injusto é esse sistema capitalista e sai do trabalho.
Mirko recebe atribuições até que apenas um funcionário permaneça na corporação — O próprio Mirko. Então ele completa esta tarefa, recebe 1 moeda e sai da corporação.
Ele se perguntou quantas moedas cada ex-funcionário recebeu no total. Ajude-o com isso.
Entrada:
A primeira linha contém um número natural N (1 ≤ N ≤ 2·10
5) — o número de funcionários da empresa. A próxima linha contém N-1 números a
2, a
3, ... a
n (1 ≤ a
i <i), a
i — número do chefe do i-ésimo funcionário.
Saída:
Imprima N números, o i-ésimo número deve indicar quantas moedas o i-ésimo funcionário recebeu.
Exemplos:
| Entrada |
Saída |
3
1 1
| 5 1 1 |
5
1 2 2 4
| 13 8 1 3 1 |
Explicações:
A seguir está uma descrição do segundo exemplo.
Mirko passa a primeira tarefa para o trabalhador 2, que a passa para o trabalhador 3, que completa a tarefa. Assim, o trabalhador 3 recebe uma moeda, o trabalhador 2 — duas moedas, e o trabalhador 1, o próprio Mirko, — três moedas. Depois disso, o funcionário 3 se demite.
Mirko passa a segunda tarefa para o trabalhador 2, que a passa para o trabalhador 4, que imediatamente passa a tarefa para o trabalhador 5, que completa a tarefa. Depois disso, o trabalhador 5 recebe uma moeda, o trabalhador 4 — duas moedas, trabalhador 2 — três moedas e Mirko — quatro moedas. Funcionário 5 sai.
Depois de completar a terceira tarefa, o trabalhador 4 recebe uma moeda, o trabalhador 2 — duas moedas e Mirko — três moedas, após o que o funcionário 4 se demite.
Depois de completar a quarta tarefa, o trabalhador 2 recebe uma moeda e Mirko — duas moedas, após o que o segundo funcionário se demite.
Por fim, a quinta tarefa é realizada pelo próprio Mirko, recebendo uma moeda por isso, após a qual o processo é interrompido.
No total, Mirko recebeu 13 moedas, um funcionário 2 — 8 moedas, trabalhador 4 — 3 moedas e trabalhadores 3 e 5 — uma moeda.