问题描述

给定一个排列 $P=(P _ 1,P _ 2,\\ldots,P _ N)$，其中包含数字 $(1,2,\\ldots,N)$。

对于所有的 $i\\ (1\\leq i\\leq N)$，求以下值：

• $D _ i=\\displaystyle\\min_{j\\neq i}\\left\\lparen\\left\\lvert P _ i-P _ j\\right\\rvert+\\left\\lvert i-j\\right\\rvert\\right\\rparen$。

什么是排列？排列 $(1,2,\\ldots,N)$ 是通过重新排列 $(1,2,\\ldots,N)$ 得到的序列。换句话说，如果且仅当每个 $i\\ (1\\leq i\\leq N)$ 在序列 $A$ 中只出现一次时，长度为 $N$ 的序列 $A$ 是排列 $(1,2,\\ldots,N)$。

约束条件

• $2 \\leq N \\leq 2\\times10^5$
• $1 \\leq P _ i \\leq N\\ (1\\leq i\\leq N)$
• $i\\neq j\\implies P _ i\\neq P _ j$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出输入：

$N$ $P _ 1$ $P _ 2$ $\\ldots$ $P _ N$

输出

按照 $i$ 的升序，以空格分隔的形式打印 $D _ i\\ (1\\leq i\\leq N)$。

示例输入 1

4
3 2 4 1

示例输出 1

2 2 3 3 

例如，对于 $i=1$，

• 如果 $j=2$，我们有 $\\left\\lvert P _ i-P _ j\\right\\rvert=1$ 和 $\\left\\lvert i-j\\right\\rvert=1$；
• 如果 $j=3$，我们有 $\\left\\lvert P _ i-P _ j\\right\\rvert=1$ 和 $\\left\\lvert i-j\\right\\rvert=2$；
• 如果 $j=4$，我们有 $\\left\\lvert P _ i-P _ j\\right\\rvert=2$ 和 $\\left\\lvert i-j\\right\\rvert=3$。

因此，当 $j=2$ 时，值最小，即 $\\left\\lvert P _ i-P _ j\\right\\rvert+\\left\\lvert i-j\\right\\rvert=2$，所以 $D _ 1=2$。

示例输入 2

7
1 2 3 4 5 6 7

示例输出 2

2 2 2 2 2 2 2 

示例输入 3

16
12 10 7 14 8 3 11 13 2 5 6 16 4 1 15 9

示例输出 3

3 3 3 5 3 4 3 3 4 2 2 4 4 4 4 7