← 返回题目列表

AtCoder · stpc2025_1_b

B. 增加掉期

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

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