J - Balanced Permutation
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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