Permutation Distance

题目描述

你被给出一个排列 $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$。

输入格式

输入由标准输入给出，格式如下： $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

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

提示

$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$ 输入中的所有数值均为整数。例如，对于 $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$。

标签: AtCoder|abc283F

来源

AtCoder|abc283F