Walking on the Wire

Byteasar is a famous circus performer known for his tightrope walking skills. In his show, there are n wires hanging from the ceiling of the circus tent. When viewed from above and placed on a coordinate system, the i-th wire (for i = 1,2,...,n) connects the point \((i,0)\) with the point \((p_i,1)\), where \(p_1, p_2, \ldots, p_n\) is a permutation of \(\{1,2,\ldots,n\}\).

The wires are all suspended at similar heights. Two wires, say the i-th and j-th, intersect if and only if they cross each other. In other words, they intersect if and only if either

[ \text{if } i < j \text{ then } p_i > p_j, \quad \text{or} \quad i > j \text{ then } p_i < p_j. ]

Byteasar begins his performance standing on one of the wires. The audience then selects a target wire. Byteasar can walk along a wire without effort, but switching from one wire to another is only possible at an intersection point of the two wires. When moving from one wire to another, he always chooses a route that minimizes the number of intersection points he needs to traverse. The unique exception is when it is impossible to reach the target wire via intersections; in that case, Byteasar simply thanks the audience politely and retreats backstage, without crossing any intersections.

For each wire, Byteasar wishes to know the sum of the minimum number of intersections he would have to cross if the audience chooses any wire as the target within the same connected component (i.e. when there exists a sequence of intersections connecting the two wires). Formally, for every wire \(i\), let

[ S_i = \sum_{j \in C(i)} d(i,j), ]

where \(C(i)\) is the set of wires in the same connected component as wire \(i\) (including \(i\) itself) and \(d(i,j)\) is the minimum number of intersections required to go from wire \(i\) to wire \(j\) (with \(d(i,i) = 0\)).

Your task is to help Byteasar by computing \(S_i\) for every wire \(i = 1,2,\ldots,n\).

inputFormat

The first line contains an integer \(n\) (\(1 \le n\)). The second line contains \(n\) distinct integers \(p_1,p_2,\ldots,p_n\) — a permutation of \(\{1,2,\ldots,n\}\).

outputFormat

Output \(n\) integers \(S_1,S_2,\ldots,S_n\) separated by spaces. Here, \(S_i\) is the sum of minimum intersections required for wire \(i\) to reach every other wire in its connected component (with \(S_i\) including a \(0\) contribution for \(i\) itself).

sample

3
3 1 2

2 3 3