题目描述

最近，小贝忙于学习，考试和比赛。现在她想出去在城市里逛逛放松一下。

城市有 $n$ 个路口，从 $1$ 到 $n$ 编号。小贝家在 $1$ 号路口，她从 $1$ 号路口出发，走过一系列的路口。从路口 $i$ 到路口 $j$ 需要消耗 $|i - j|$ 单位的能量。她走过一系列路口 $p_1​ = 1, p_2​, ..., p_k$​ 消耗的总能量等于 $\sum_{i=1}^{k-1} |p_{i} - p_{i+1}|$。

当然，如果没有小路，一味步行是比较无聊的。小路是特别的路径，能让小贝从一个路口到另一个路口只消耗 $1$ 单位的能量。小贝的城市总共恰好有 $n$ 条小路，第 $i$ 条小路允许小贝从路口 $i$ 走到路口 $a_i\ (i ≤ a_i ≤ a_{i+1})$（但不能反方向走），因此每个路口都有且只有一条小路。严格来说，如果小贝选择一系列路口 $p_1 = 1, p_2, ..., p_k$，那么对于每个 $1 ≤ i < k$ 满足 $p_{i+1} = a_{p_i}$，并且 $a_{p_i} ≠ p_i$，从路口 $p_i$ 到路口 $p_{i+1}$，小贝只会消耗 $1$ 单位能量，而不是 $|p_i - p_{i+1}|$。 例如，如果小贝选择路口序列 $p_1 = 1, p_2 = a_{p_1}, p_3 = a_{p_2}, ..., p_k = a_{p_{k-1}}$，她总共消耗 $k - 1$ 单位的能量。

在她开始闲逛之前，她请你帮她计算从她家到达每个路口最少消耗多少能量。

输入格式

第一行包含一个整数 $n\ (1 ≤ n ≤ 200 000)$，表示小贝城市的路口数量。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n\ (i ≤ a_i ≤ n, a_i\le a_{i+1})$，给出小贝城市的小路，允许小贝只消耗 $1$ 单位能量从路口 $i$ 到路口 $a_i$。请注意小路不能走反方向（从 $a_i$ 到 $i$）。

输出格式

输出 $n$ 个整数 $m_1,m_2, ..., m_n$，其中 $m_i$，表示从路口 $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