Corporate Task Delegation

Mirko has become the CEO of a huge corporation with N employees, numbered from 1 to N (with Mirko being 1). Every employee (except Mirko) has exactly one boss, forming a tree structure. When a task is received, Mirko delegates it to his active assistant with the smallest index. That assistant, in turn, passes the task to his active assistant with the smallest index, and so on, until the task reaches an employee without any active assistants. This employee must complete the task.

The payment scheme is as follows: the employee who completes the task earns 1 coin, his boss earns 2 coins, his boss earns 3 coins, and so on up to Mirko, who earns as many coins as there are people in the delegation chain. Immediately after completing the task, the employee who actually did the job quits.

This entire process is repeated until only Mirko remains, at which point he completes one final task and earns 1 coin. Your task is to calculate the total number of coins each employee earned during this sequence of tasks (even if they later quit).

Note: When delegating, each boss always chooses the active assistant with the smallest label. The challenge requires simulating the dynamic removal of employees as they quit.

inputFormat

The first line contains an integer N (1 ≤ N ≤ 200,000), representing the number of employees.

The second line contains N-1 integers. For each i from 2 to N, the i-th integer indicates the boss of employee i.

outputFormat

Output N integers separated by spaces. The i-th integer should represent the total coins earned by employee i.

sample

7
1 1 2 2 3 3

17 5 5 1 1 1 1