| Codeforces Round 361 (Div. 2) |
|---|
| Закончено |
Только что Майк был очень занят подготовкой к экзаменам и контестам, теперь же, чтобы проветриться, он решил прогуляться мимо городских достопримечательностей.
Город состоит из n перекрестков с номерами от 1 до n. Майк начинает прогулку от своего дома и идет вдоль определенной последовательности перекрестков. Чтобы дойти от перекрестка i до перекрестка j, Майку нужно потратить |i - j| единиц энергии. Суммарное количество энергии, потраченное Майком при прогулке вдоль последовательности перекрестков p1 = 1, p2, ..., pk равно 
единицам энергии.
Конечно, прогулки были бы скучными без переулков. Переулком называется специальный путь, позволяющий Майку идти от одного перекрестка к другому, используя лишь 1 единицу энергии. Всего в городе Майка ровно n переулков, i-й из них позволяет пройти от перекрестка с номером i к перекрестку с номером ai (i ≤ ai ≤ ai + 1) (но не в противоположном направлении), то есть для каждого перекрестка существует ровно один исходящий переулок. Формально, если Майк выберет последовательность p1 = 1, p2, ..., pk, то для каждого 1 ≤ i < k удовлетворяющего pi + 1 = api and api ≠ pi Майк потратит всего 1 единицу энергии вместо |pi - pi + 1| единиц, прогуливаясь от перекрестка pi к перекрестку pi + 1. К примеру, если Майк решит выбрать последовательность p1 = 1, p2 = ap1, p3 = ap2, ..., pk = apk - 1, то потратит суммарно k - 1 единицу энергии на прогулку вдоль перекрестков.
Перед тем как отправиться в путь, Майк просит вас для каждого перекрестка посчитать минимальное количество энергии, необходимое, чтобы дойти до него от дома Майка. Формально, для каждого 1 ≤ i ≤ n Майка интересует минимально возможное суммарное количество энергии некоторой последовательности p1 = 1, p2, ..., pk = i.
В первой строке содержится целое число n (1 ≤ n ≤ 200 000) — количество перекрестков в городе Майка.
Во второй строке содержатся n чисел a1, a2, ..., an (i ≤ ai ≤ n , 
, описывающие переулки города. i-й из них позволяет Майку дойти от переулка i до переулка ai за одну единицу энергии. Заметьте, что переулки не позволяют проход в обратном направлении (от ai к i).
В единственной строке выведите n чисел m1, m2, ..., mn, где mi означает наименьшее количество единиц энергии, которое Майку нужно потратить, чтобы добраться от перекрестка 1 до перекрестка i.
3
2 2 3
0 1 2
5
1 2 3 4 5
0 1 2 3 4
7
4 4 4 4 7 7 7
0 1 2 1 2 3 3
В первом примере подходящими являются следующие последовательности:
1: 1; m1 = 0;
2: 1, 2; m2 = 1;
3: 1, 3; m3 = |3 - 1| = 2.
Во втором примере последовательность для любого перекрестка 1 < i всегда имеет вид 1, i, а mi = |1 - i|.
В третьем примере входных данных можно рассматривать следующие последовательности:
1: 1; m1 = 0;
2: 1, 2; m2 = |2 - 1| = 1;
3: 1, 4, 3; m3 = 1 + |4 - 3| = 2;
4: 1, 4; m4 = 1;
5: 1, 4, 5; m5 = 1 + |4 - 5| = 2;
6: 1, 4, 6; m6 = 1 + |4 - 6| = 3;
7: 1, 4, 5, 7; m7 = 1 + |4 - 5| + 1 = 3.
