最近,Mike 非常忙于学习考试和比赛。现在他打算去城里观光一下,放松一下。
城市由 n 个交叉路口组成,编号从 1 到 n。迈克从位于 1 号十字路口的家开始步行,并沿着一系列十字路口行驶。从编号 i 的交叉路口步行到交叉路口 j 需要 |i - j|能量单位。 Mike 访问一系列交叉点 p1 = 1, p2, ..., pk 所花费的总能量等于 $${\displaystyle \sum _ { i = 1 } ^ { k - 1 } | p _ { i } - p _ { i + 1 } |}$$ 单位能量。
当然,如果没有捷径,步行就会很无聊。捷径是一条特殊的路径,允许迈克从一个十字路口走到另一个十字路口,只需要 1 个单位的能量。 Mike所在的城市正好有n条捷径,其中第i条允许从路口i步行到路口ai (i ≤ ai ≤ ai + 1)(但不能反向),因此每个路口都恰好有一条捷径。形式上,如果 Mike 选择序列 p1 = 1, p2, ..., pk,那么对于每个 1 ≤ i < k 满足 pi + 1 = api 且 api ≠ pi 的情况,Mike 将仅花费 1 个单位的能量,而不是 |pi - pi + 1|从交叉点 pi 步行到交叉点 pi + 1。例如,如果 Mike 选择序列 p1 = 1、p2 = ap1、p3 = ap2、...、pk = apk - 1,则他在围绕它们行走时正好花费 k - 1 单位的总能量。
在继续他的冒险之前,迈克要求你找到从他家到达每个十字路口所需的最小能量。形式上,对于每个 1 ≤ i ≤ n,Mike 感兴趣的是找到某个序列 p1 = 1, p2, ..., pk = i 的最小可能总能量。
输入
第一行包含一个整数 n (1 ≤ n ≤ 200 000) — Mike 的城市路口数量。
第二行包含 n 个整数 a1, a2, ..., an (i ≤ ai ≤ n , $$a_{i} \leq a_{i+1} \forall i < n$$,描述 Mike 城市的捷径,允许仅使用 1 个单位的能量从交叉路口 i 步行到交叉路口 ai。请注意,捷径不允许沿相反方向行走(从 ai 到 i)。
输出
在唯一的一行中打印 n 个整数 m1, m2, ..., mn,其中 mi 表示从交叉路口 1 步行到交叉路口 i 所需的最少总能量。
示例
输入 #1
3 2 2 3
输出 #1
0 1 2
输入 #2
5 1 2 3 4 5
输出 #2
0 1 2 3 4
输入 #3
7 4 4 4 4 7 7 7
输出 #3
0 1 2 1 2 3 3
注意
在第一个示例中,所需的序列是:
1:1; m1=0;
2: 1, 2;米2=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。