Bajtazar is a world-famous circus performer who specializes in walking on tightropes and moving between them. During his famous trick, $n$ ropes are stretched under the ceiling of the circus tent. If we look at the tent plan from above and impose a coordinate system, the $i$-th rope (for $i = 1, 2, \dots, n$) is stretched from the point $(i, 0)$ to $(p_i, 1)$, where the sequence $p_1, p_2, \dots, p_n$ is a permutation of numbers from $1$ to $n$.

Bajtazar begins the trick standing on one of the ropes and asks the audience to provide him with the number of a rope. His goal is to end up standing on that rope. Bajtazar is very skilled at moving along the ropes, but moving from one to another is quite complicated. Since he is very brave but not foolish, he can only move from one rope to another if their corresponding segments intersect. All ropes are suspended at a similar height, so such a maneuver always succeeds, but it is quite tiring. For this reason, Bajtazar chooses a route that minimizes the number of transitions between different ropes. The exception is the situation where reaching the target rope in the described way is not possible – then Bajtazar politely thanks the audience for the performance and returns backstage, thus performing zero transitions.

Bajtazar is not sure, however, from which rope he should start his performance this time. For each of them, he would like to know the sum of the minimum numbers of transitions he must perform, over all possible choices of the audience. Help him and write a program that calculates these values.

Input

The first line of standard input contains one integer $n$ ($1 \le n \le 200\,000$), representing the number of ropes stretched in the circus tent.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$; for $i \neq j$ it holds that $p_i \neq p_j$), as described in the problem statement.

Output

The only line of output should contain $n$ integers, where the $i$-th of them should be equal to the sum of the minimum numbers of transitions that Bajtazar will have to perform depending on the rope number provided by the audience, assuming he starts on the $i$-th rope.

Examples

Input 1

7
2 1 4 7 3 6 5

Output 1

1 1 9 5 6 7 7

Note

The ropes stretched in the example test look as follows:

The minimum number of transitions between them is presented below, where the row number corresponds to the starting rope number, and the column number corresponds to the rope number provided by the audience. The numbers in the program output should be equal to the sums of values in the respective rows:

Row 1: 0 1 0 0 0 0 0 Row 2: 1 0 0 0 0 0 0 Row 3: 0 0 0 2 1 3 3 Row 4: 0 0 2 0 1 1 1 Row 5: 0 0 1 1 0 2 2 Row 6: 0 0 3 1 2 0 1 Row 7: 0 0 3 1 2 1 0