配点 : 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