26727번 - Chodzenie po linie 다국어

Bajtazar jest światowej sławy cyrkowcem, który specjalizuje się w chodzeniu po naciągniętych linach oraz przechodzeniu między nimi. Podczas jego słynnego triku pod sufitem namiotu cyrkowego rozciągniętych jest n lin. Jeśli spojrzymy na plan namiotu od góry i nałożymy na niego układ współrzędnych, to i-ta z lin (dla i = 1, 2, . . . , n) rozciągnięta jest od punktu (i, 0) do (p_i, 1), gdzie ciąg p₁, p₂, . . . , p_n jest permutacją liczb od 1 do n.

Bajtazar rozpoczyna trik stojąc na jednej z lin i prosi publikę o podanie mu numeru jakiejś liny. Jego celem jest doprowadzić do stanięcia na niej. Bajtazar jest bardzo wprawny w przemieszczaniu się po linach, jednak przechodzenie z jednej na drugą jest dość skomplikowane. Ponieważ jest bardzo odważny, ale nie głupi, to może on przejść z jednej liny na drugą tylko jeśli odpowiadające im odcinki się przecinają. Wszystkie liny zawieszone są na podobnej wysokości, więc taki manewr zawsze się udaje, jednak jest dość męczący. Z tego względu Bajtazar wybiera trasę, która minimalizuje liczbę przejść pomiędzy różnymi linami. Wyjątkiem jest sytuacja, w której dotarcie do docelowej liny w opisany sposób nie jest możliwe – wtedy Bajtazar grzecznie dziękuje za występ i wraca za kulisy, przez co nie wykonuje żadnego przejścia.

Bajtazar nie jest jednak pewien, od której liny powinien tym razem rozpocząć swój występ. Dla każdej z nich chciałby poznać sumę minimalnych liczb przejść, które musi wykonać, po wszystkich możliwych wyborach publiki. Pomóż mu i napisz program, który obliczy te wartości.

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 200 000), oznaczająca liczbę lin rozciągniętych w cyrkowym namiocie.

W drugim wierszu znajduje się n liczb całkowitych p₁, p₂, . . . , p_n (1 ≤ p_i ≤ n; dla i ≠ j zachodzi p_i ≠ p_j), opisanych w treści zadania.

W jedynym wierszu wyjścia powinno znaleźć się n liczb całkowitych, gdzie i-ta z nich powinna być równa sumie po minimalnych liczbach przejść, które będzie musiał wykonać Bajtazar zależnie od numeru liny podanego przez publikę, zakładając że zacznie na i-tej linie.

Wyjaśnienie przykładu: Rozciągnięte w teście przykładowym liny wyglądają następująco:

Minimalną liczbę przejść pomiędzy nimi prezentuje poniższa tabelka, gdzie numer rzędu odpowiada numerowi startowej liny, a numer kolumny odpowiada numerowi liny podanemu przez publikę. Liczby na wyjściu programu powinny być równe sumom wartości w kolejnych rzędach: