AT_abc283_f [ABC283F] Permutation Distance

题目描述

给定一个 $(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( |P_i - P_j| + |i - j| \right)$

排列是指将 $(1,2,\ldots,N)$ 重新排列得到的数列。也就是说，长度为 $N$ 的数列 $A$，当且仅当 $i\ (1\leq i\leq N)$ 在其中恰好出现一次时，$A$ 是 $(1,2,\ldots,N)$ 的一个排列。

输入格式

输入以以下格式从标准输入读入。

$N\ P_1\ P_2\ \ldots\ P_N$

输出格式

请按 $i$ 的升序，用空格分隔输出 $D_i\ (1\leq i\leq N)$。

输入输出样例 #1

输入 #1

4
3 2 4 1

输出 #1

2 2 3 3

输入输出样例 #2

输入 #2

7
1 2 3 4 5 6 7

输出 #2

2 2 2 2 2 2 2

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $2 \leq N \leq 2\times 10^5$
• $1 \leq P_i \leq N\ (1\leq i\leq N)$
• $i\neq j \implies P_i\neq P_j$
• 输入均为整数

样例解释 1

例如，对于 $i=1$：

• 当 $j=2$ 时，$|P_i - P_j|=1,\ |i-j|=1$。
• 当 $j=3$ 时，$|P_i - P_j|=1,\ |i-j|=2$。
• 当 $j=4$ 时，$|P_i - P_j|=2,\ |i-j|=3$。

因此，当 $j=2$ 时 $|P_i - P_j|+|i-j|=2$，为最小值，所以 $D_1=2$。

由 ChatGPT 4.1 翻译