配点 : 100 点
問題文
(1, 2, \dots, N) 的排列 给出了 P = (P_1, P_2, \dots, P_N) 。 对于
长度 小于或等于 N - 1 的正整数序列 给出了 T = (T_1, T_2, \dots, T_{N - 1}) ,f(T) 定义为以下问题中的输出值。 对
你 P 执行任意次数的操作 (0 次)。 第t 个操作执行以下操作: 满足
- T_i \le t 小于 i 列按升序排列 按照 I 。j = 1, 2, \dots, |I| 的顺序, 执行替换为P_{I_j} 和 按字典顺序比较 P_{I_j + 1} 。 ( 请注意,它不是 P_{I_j + 1} 是 您也可以写 P_{I_{j + 1}} 。 ) 请输出按升序对
P 进行排序所需的最少运算次数。但是,如果您无法排序 {10}^{100} 。 须满足
所有正整数序列 对于 T 以同样的方式定义 f(T) 的最小值。此外,在这个问题的约束下, 我们可以证明f(T) < {10}^{100} 小于 T 总是存在。
制約
- 所有输入均为整数
- 2 \le N \le 5000
- 1 \le P_i \le N
- P_i \ne P_j (i \ne j)
部分点
- 附加限制 如果正确答案是满足 N \le 400 的数据集 给出 30 点。 如果您正确回答了所有满足
入力
输入按以下格式给出。
N P_1 P_2 \cdots P_N
出力
打印答案。 来自
入力例 1
4 4 2 1 3
出力例 1
2
T=(2,1,2) 以1 次操作中 P=(4,1,2,3) 变为 通过2 次操作中 P=(1,2,3,4) ,所以f(T) = 2 成立。f(T) < 2 小于 T 不存在,所以答案是 2 。 对于
入力例 2
20 15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
出力例 2
39