Problem Description

Mirko has become CEO of a huge corporation. This corporation consists of \( N \) people, labeled from 1 to \( N \), and Mirko is labeled 1. The corporation is structured so that each employee (except Mirko) has a boss, and we say that employee is an assistant to that boss. Each boss can have multiple assistants, but still reports to their boss. This holds for everyone except Mirko, who is at the top of the pyramid and doesn’t have a boss, but has his assistants.

When Mirko gets a task from the investors, he then delegates that task to his assistant with the minimal number. This assistant then delegates the task to their assistant with the minimal number, and this process repeats until the task is given to an unlucky person without an assistant, who then must do the task.

This is when the real problems begin. The person that did the task gets paid 1 coin, the boss of that person gets 2 coins, the boss of that person gets 3 coins, and so on, all the way to Mirko, who gets as many coins as there are people in this sequence. After that, the employee that really did the job realizes how unfair the system is and quits their job out of principle.

When it comes to doing the next task in the corporation, there is a person less, so maybe the paychecks are less, but the work must continue. Tasks are piling up, so the whole procedure (assigning a new task, doing it, dividing paychecks and the person doing the task quitting) repeats until Mirko is left alone in the corporation and does his first (also his last) task.

Of course, Mirko will have amassed quite a fortune until then, but he also wants to know how much money each of the employees earned.

Input Format

The first line of input contains the positive integer \( N \) (\( 2 \leq N \leq 2 \cdot 10^5 \)), the number of employees (including Mirko).

The following line contains \( N-1 \) positive integers \( a_2, a_3, \ldots, a_N \) (\( 1 \leq a_i < i \)), where \( a_i \) denotes the boss of employee \( i \).

Output Format

You must output a single line consisting of \( N \) numbers, the \( i \)-th number corresponding to the amount of money earned by the \( i \)-th employee.

Sample Input and Output

Sample Input #1

3
1 1

Sample Output #1

5 1 1

Sample Input #2

5
1 2 2 4

Sample Output #2

13 8 1 3 1

Notes/Hints

In test cases worth 50% of total points, it will hold \( 2 \leq N \leq 5000 \).

Clarification of the second test case:

Mirko assigns the first task to employee 2, who then assigns it to employee 3, who then does it. For this, employee 3 gets 1 coin, employee 2 gets 2 coins, and employee 1 (Mirko) gets 3 coins. Employee 3 then quits.

Mirko assigns the second task to employee 2, who then assigns it to employee 4 (because employee 3 quit), who then assigns it to employee 5, who then does it. For this, employee 5 gets 1 coin, employee 4 gets 2 coins, employee 2 gets 3 coins, and employee 1 gets 4 coins. Employee 5 then quits.

The procedure is repeated for a total of 5 tasks.

In total, Mirko gets 13 coins, employee 2 gets 8, employee 4 gets 3, and employee 3 and 5 each get 1 coin.

见题面 Input 部分

见题面 Output 部分