CF689B.Mike and Shortcuts

Recently, Mike was very busy with studying for exams and contests. Now he is going to chill a bit by doing some sight seeing in the city.

City consists of n intersections numbered from 1 to n. Mike starts walking from his house located at the intersection number 1 and goes along some sequence of intersections. Walking from intersection number i to intersection j requires |i - j| units of energy. The total energy spent by Mike to visit a sequence of intersections _p_1 = 1, _p_2, ..., p__k is equal to units of energy.

Of course, walking would be boring if there were no shortcuts. A shortcut is a special path that allows Mike walking from one intersection to another requiring only 1 unit of energy. There are exactly n shortcuts in Mike's city, the i__th of them allows walking from intersection i to intersection a__i (i ≤ a__i ≤ a__i + 1) (but not in the opposite direction), thus there is exactly one shortcut starting at each intersection. Formally, if Mike chooses a sequence _p_1 = 1, _p_2, ..., p__k then for each 1 ≤ i < k satisfying p__i + 1 = a__p__i and a__p__i ≠ p__i Mike will spend only 1 unit of energy instead of |p__i - p__i + 1| walking from the intersection p__i to intersection p__i + 1. For example, if Mike chooses a sequence _p_1 = 1, _p_2 = _a__p_1, _p_3 = _a__p_2, ..., p__k = a__p__k - 1, he spends exactly k - 1 units of total energy walking around them.

Before going on his adventure, Mike asks you to find the minimum amount of energy required to reach each of the intersections from his home. Formally, for each 1 ≤ i ≤ n Mike is interested in finding minimum possible total energy of some sequence _p_1 = 1, _p_2, ..., p__k = i.

最近，Mike 一直在忙于备考和参加编程竞赛。现在他打算通过在城市中观光来稍微放松一下。

这座城市由 $n$ 个路口组成，编号从 $1$ 到 $n$。Mike 从位于路口 $1$ 的家出发，沿着某个路口序列行走。从路口 $i$ 走到路口 $j$ 需要 $|i - j|$ 单位的能量。Mike 访问路口序列 $p_1 = 1,\ p_2,\ \dots,\ p_k$ 所消耗的总能量为

单位能量。

当然，如果没有捷径，步行就会很乏味。所谓“捷径”，是一种特殊路径，允许 Mike 仅花费 $1$ 单位能量就从一个路口走到另一个路口。Mike 所在的城市中恰好有 $n$ 条捷径，其中第 $i$ 条捷径允许从路口 $i$ 走到路口 $a_i$（满足 $i \le a_i \le a_i + 1$）（但不允许反向通行），即每个路口恰好有一条以它为起点的捷径。形式化地说：若 Mike 选择序列 $p_1 = 1,\ p_2,\ \dots,\ p_k$，则对每个满足 $1 \le i < k$ 且 $p_{i+1} = a_{p_i}$ 以及 $a_{p_i} \ne p_i$ 的下标 $i$，Mike 从路口 $p_i$ 走到 $p_{i+1}$ 时仅需消耗 $1$ 单位能量，而非原本的 $|p_i - p_{i+1}|$。例如，若 Mike 选择序列 $p_1 = 1,\ p_2 = a_{p_1},\ p_3 = a_{p_2},\ \dots,\ p_k = a_{p_{k-1}}$，则他绕行这些捷径所消耗的总能量恰好为 $k - 1$ 单位。

在出发探险前，Mike 请你帮他计算：从家（路口 $1$）出发，到达每个路口所需的最少能量。形式化地，对每个 $1 \le i \le n$，Mike 想要求出某条以 $p_1 = 1$ 开始、以 $p_k = i$ 结束的序列 $p_1,\ p_2,\ \dots,\ p_k$ 所对应的最小可能总能量。

The first line contains an integer n (1 ≤ n ≤ 200 000) — the number of Mike's city intersection.

The second line contains n integers _a_1, _a_2, ..., a__n (i ≤ a__i ≤ n , , describing shortcuts of Mike's city, allowing to walk from intersection i to intersection a__i using only 1 unit of energy. Please note that the shortcuts don't allow walking in opposite directions (from a__i to i).

第一行包含一个整数 $ n $（$ 1 \leq n \leq 200,000 $）——表示 Mike 所在城市路口的数量。

第二行包含 $ n $ 个整数 $ a_1,,a_2,,\dots,,a_n $（满足 $ i \leq a_i \leq n $，），描述了 Mike 所在城市的捷径：利用这些捷径，可以从第 $ i $ 个路口仅消耗 1 单位能量到达第 $ a_i $ 个路口。请注意，这些捷径是单向的，即不允许反向通行（从 $ a_i $ 到 $ i $）。

In the only line print n integers _m_1, _m_2, ..., m__n, where m__i denotes the least amount of total energy required to walk from intersection 1 to intersection i.

在唯一的一行中输出 $n$ 个整数 $m_1,\,m_2,\,...,\,m_n$，其中 $m_i$ 表示从交叉路口 1 走到交叉路口 $i$ 所需的最少总能量。

In the first sample case desired sequences are:

1: 1; _m_1 = 0;

2: 1, 2; _m_2 = 1;

3: 1, 3; _m_3 = |3 - 1| = 2.

In the second sample case the sequence for any intersection 1 < i is always 1, i and m__i = |1 - i|.

In the third sample case — consider the following intersection sequences:

1: 1; _m_1 = 0;

2: 1, 2; _m_2 = |2 - 1| = 1;

3: 1, 4, 3; _m_3 = 1 + |4 - 3| = 2;

4: 1, 4; _m_4 = 1;

5: 1, 4, 5; _m_5 = 1 + |4 - 5| = 2;

6: 1, 4, 6; _m_6 = 1 + |4 - 6| = 3;

7: 1, 4, 5, 7; _m_7 = 1 + |4 - 5| + 1 = 3.

在第一个样例中，满足要求的序列如下：

1: 1；$m_1 = 0$；

2: 1, 2；$m_2 = 1$；

3: 1, 3；$m_3 = |3 - 1| = 2$。

在第二个样例中，对任意交点 $i > 1$，对应的序列恒为 $1,\,i$，且 $m_i = |1 - i|$。

在第三个样例中，考虑以下交点序列：

1: 1；$m_1 = 0$；

2: 1, 2；$m_2 = |2 - 1| = 1$；

3: 1, 4, 3；$m_3 = 1 + |4 - 3| = 2$；

4: 1, 4；$m_4 = 1$；

5: 1, 4, 5；$m_5 = 1 + |4 - 5| = 2$；

6: 1, 4, 6；$m_6 = 1 + |4 - 6| = 3$；

7: 1, 4, 5, 7；$m_7 = 1 + |4 - 5| + 1 = 3$。