Bajtazar 是一位世界闻名的马戏团演员，擅长走钢丝以及在钢丝之间穿梭。在他著名的表演中，马戏团帐篷的顶部拉着 $n$ 根钢丝。如果我们从上方俯瞰帐篷并建立坐标系，第 $i$ 根钢丝（对于 $i = 1, 2, \dots, n$）是从点 $(i, 0)$ 拉到点 $(p_i, 1)$ 的线段，其中序列 $p_1, p_2, \dots, p_n$ 是 $1$ 到 $n$ 的一个排列。

Bajtazar 开始表演时站在其中一根钢丝上，并请观众指定一根钢丝的编号。他的目标是移动到那根钢丝上。Bajtazar 在钢丝上移动非常熟练，但从一根钢丝切换到另一根钢丝相当复杂。由于他非常勇敢但不鲁莽，他只有在对应的线段相交时才能从一根钢丝切换到另一根。所有的钢丝都悬挂在相同的高度，因此这种操作总是可以成功，但非常耗费体力。因此，Bajtazar 会选择一条路径，使得在不同钢丝之间的切换次数最少。如果无法通过上述方式到达目标钢丝，则是一个例外情况——此时 Bajtazar 会礼貌地感谢观众并退场，因此不进行任何切换。

Bajtazar 不确定这次应该从哪根钢丝开始表演。对于每一根钢丝，他都想知道在所有可能的观众选择下，他必须执行的最小切换次数之和。请帮助他编写一个程序来计算这些值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示马戏团帐篷中拉着的钢丝数量。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$；对于 $i \neq j$ 有 $p_i \neq p_j$)，如题目所述。

输出格式

输出一行，包含 $n$ 个整数，其中第 $i$ 个数应等于当 Bajtazar 从第 $i$ 根钢丝开始时，针对观众给出的所有可能钢丝编号，他所需执行的最小切换次数之和。

样例

输入格式 1

7
2 1 4 7 3 6 5

输出格式 1

1 1 9 5 6 7 7

说明 1

示例测试中的钢丝布局如下：

钢丝之间的最小切换次数如下所示，其中行号对应起始钢丝编号，列号对应观众指定的钢丝编号。程序输出的数字应等于各行数值之和：