排列距离

题目描述

给定 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_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)$ 重新排列后得到的序列。换言之,长度为 $N$ 的序列 $A$ 是 $(1,2,\ldots,N)$ 的排列,当且仅当每个 $i\ (1\leq i\leq N)$ 在 $A$ 中恰好出现一次。

输入格式

输入按以下格式从标准输入给出:

$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 

数据范围

• $2 \le N \le 2\times10^5$
• $1 \le P_i \le N\ (1\leq i\leq N)$
• $i\neq j\implies P_i\neq P_j$
• 输入中的所有值均为整数。