P9265 [PA 2022] Walking on a Tightrope

**This problem is translated from [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Round 5 [Chodzenie po linie](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/lin/).** Byteasar is a world-famous circus performer. He is good at walking on tightropes and moving between them. In his famous show, there are $n$ tightropes stretched under the circus tent ceiling. If we look at the tent from above and place it on a coordinate plane, the $i$-th tightrope $(i=1,2,\ldots,n)$ connects the point $(i,0)$ and the point $(p_i,1)$, where the sequence $p_1,p_2,\ldots,p_n$ is a permutation of the integers from $1$ to $n$. Byteasar starts the show standing on one of the tightropes, and the audience gives him the number of some tightrope. His goal is to end up standing on the tightrope chosen by the audience. Byteasar can move very well along a tightrope, but moving from one tightrope to another is quite complicated. Since he is brave but not foolish, he can move from one tightrope to another only when the two tightropes intersect. All tightropes hang at similar heights, so such a move always succeeds, but it is very tiring. For this reason, Byteasar will choose a route that uses the minimum possible number of intersections between different tightropes. The only exception is when it is impossible to reach the target tightrope in this way—in that case, Byteasar will politely thank the audience and return backstage, so he will not cross anything. However, Byteasar is not sure which tightrope he should start his show on. For each tightrope, he wants to know, over all possible audience choices, the sum of the minimum numbers of intersections he has to pass through. Write a program to compute these values.

The first line contains an integer $n$, the number of tightropes. The second line contains $n$ integers $p_1,p_2,\ldots,p_n$, with the meaning described above.

Output one line with $n$ integers. The $i$-th integer should be the sum, over all possible audience choices, of the minimum number of intersections Byteasar must pass through if he starts from the $i$-th tightrope.

For $100\%$ of the testdata, it holds that: $1\le n\le 2 \times 10 ^ 5, 1\le p_i\le n$. It is guaranteed that for any $i,j\ (i\neq j)$, we have $p_i\neq p_j$. Translated by ChatGPT 5