← 返回题目列表

AtCoder · abc283_f

I. 排列距离

中文机器翻译题面 查看原题

分数: 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