当前没有测试数据。

F - 排列距离

分数：$500$ 分

问题描述

给定一个数列 $P=(P _ 1,P _ 2,\ldots,P _ N)$ 的排列，其中 $P=(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$。

约束

• $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)$。

4
3 2 4 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$。

7
1 2 3 4 5 6 7

2 2 2 2 2 2 2 

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

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