Problem
Mirko became the CEO of a large corporation. The company employs N people, who are numbered from 1 to N, and Mirko himself has number 1. All employees, except Mirko, have a boss. A boss can have several subordinates, but not more than one boss.
When Mirko receives an assignment from investors, he hands it over to his subordinate with the lowest number. That subordinate also passes it on to his lowest-numbered subordinate, and so on, until the job passes to an unlucky worker with no subordinates to complete it.
That worker gets 1 coin, his boss gets 2 coins, that boss's boss gets 3 coins, and so on. Then the one who actually did the job realizes how unfair this capitalist system is and quits the job.
Mirko receives assignments until only one employee remains in the corporation — Mirko himself. Then he completes this task, receives 1 coin and leaves the corporation.
He wondered how many coins each former employee received in total. Help him with this.
Input:
The first line contains one natural number N (1 ≤ N ≤ 2·10
5) — the number of company employees. The next line contains N-1 numbers a
2, a
3, ... a
n (1 ≤ a
i <i), a
i — number of the head of the i-th employee.
Output:
Print N numbers, the i-th number should indicate how many coins the i-th employee received.
Examples:
| Input |
Output |
3
1 1
| 5 1 1 |
5
1 2 2 4
| 13 8 1 3 1 |
Explanations:
The following is a description of the second example.
Mirko gives the first task to worker 2, who passes it on to worker 3, who completes the task. Thus, worker 3 receives one coin, worker 2 — two coins, and worker 1, Mirko himself, — three coins. After that, employee 3 quits.
Mirko gives the second task to worker 2, who passes it on to worker 4, who immediately passes the task to worker 5, who completes the task. After that, worker 5 receives one coin, worker 4 — two coins, worker 2 — three coins, and Mirko — four coins. Employee 5 quits.
After completing the third task, worker 4 receives one coin, worker 2 — two coins, and Mirko — three coins, after which employee 4 quits.
After completing the fourth task, worker 2 receives one coin, and Mirko — two coins, after which the second employee quits.
Finally, the fifth task is performed by Mirko himself, receiving one coin for this, after which the process stops.
In total, Mirko received 13 coins, an employee 2 — 8 coins, worker 4 — 3 coins, and workers 3 and 5 — one coin.