← 返回题目列表

AtCoder · pakencamp_2022_day3_j

J. 平衡排列

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

配点 : 100 点

問題文

长度为 N 整数序列 A 。长度 N 的排列 当 P 满足以下条件时, 求 \displaystyle \max_{1 \le i,j \le N} |iP_i-jP_j| 的最小可能值。 关于

  • 全部 i , A_i \neq -1 如果 A_i = P_i

制約

  • 1 \leq N \leq 5000
  • A_i = -1 或 给出 1 \le A_i \le N
  • i \neq j , A_i \neq -1 和 满足 A_j \neq -1 如果 A_i \neq A_j
  • 所有输入均为整数 如果有办法做到

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \ldots A_N

出力

打印答案。 求解


入力例 1

3
-1 -1 2

出力例 1

4

P=(1,3,2) 时, \displaystyle \max_{1 \le i,j \le N} |iP_i-jP_j|=5 、 P=(3,1,2) 时, \displaystyle \max_{1 \le i,j \le N} |iP_i-jP_j|=4 所以答案是 4 。


入力例 2

1
-1

出力例 2

0

入力例 3

5
2 4 5 1 3

出力例 3

13