分数: 500 点
问题陈述
给你一个排列 P=(P _ 1,P _ 2,\ldots,P _ N) of (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)。 换句话说,一个序列 A 长度 N 是一个排列 (1,2,\ldots,N) 当且仅当每个 i\ (1\leq i\leq N) 发生于 A 恰好一次。约束
- 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
输出
打印 D _ i\ (1\leq i\leq N) 按升序排列 i,用空格分隔。
示例输入 1
4 3 2 4 1
示例输出 1
2 2 3 3
例如,对于 i=1,
- if j=2,我们有 \left\lvert P _ i-P _ j\right\rvert=1 和 \left\lvert i-j\right\rvert=1;
- if j=3,我们有 \left\lvert P _ i-P _ j\right\rvert=1 和 \left\lvert i-j\right\rvert=2;
- if 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