题目描述

RE 是狮子国的宣传委员，他经常要去别的城市进行宣传。

狮子国有编号为 $1$ 到 $n$ 的 $n$ 个城市。

RE 住在 $1$ 号城市，从 $i$ 号城市走到 $j$ 号城市会花费 $|i−j|$ 点体力。

显然这是一件非常枯燥且劳累的事情。

但是，年轻人不讲武德。

RE 使用了魔法进行传送。

但是由于 RE 才只学习了初级魔法，不能随心所欲地传送，只能从 $i$ 号城市传送到 $a_i$ 号城市，并且要耗费一点体力值。

这让 RE 犯了难，所以现在他想请你帮他计算去各个城市需要的最小体力值。

输入格式

输入共若干行，第 $1$ 行只包含 $1$ 个整数 $n$，代表狮子国的城市数量。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n(i≤a_i≤n)$，代表 RE 可以从 $i$ 号城市传送到 $a_i$ 城市。

输出格式

输出共 $1$ 行，包含 $n$ 个整数 $m_1,m_2,\cdots,m_n$。

$m_i$ 代表从 $1$ 号城市到 $i$ 号城市需要花费的最小体力值。

样例

3
2 2 3

0 1 2

解释#1

目标点为 $1$ 时，最佳线路为 $1$，$m_1=0$;

目标点为 $2$ 时，最佳线路为 $1,2$，$m_2=1$;

目标点为 $3$ 时，最佳线路为 $1,3$，$m_3=|3-1|=2$。

7
4 4 4 4 7 7 7

0 1 2 1 2 3 3

解释#2

目标点为 $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$。

数据范围

• 对于 $50\%$ 的测试数据满足：$1≤n≤8$。
• 对于 $100\%$ 的测试数据满足：$1≤n≤200000$。