AT_1_stpc2025_1_b.Increasing Swaps

给定一个 $ (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 $ 次操作中，执行以下流程：

• 设 $ I $ 为满足 $ T_i \le t $ 的所有 $ i $（按升序排列）组成的序列。依次对于 $ j = 1, 2, \dots, |I| $，交换 $ P_{I_j} $ 与 $ P_{I_j+1} $（注意 $ P_{I_j+1} $ 并不是 $ P_{I_{j+1}} $）。

输出使 $ P $ 升序排序所需的最少操作次数。若无法将 $ P $ 排序，则输出 $ {10}^{100} $。

请你求出所有正整数序列 $ T $ 中 $ f(T) $ 的最小值。可以证明，在本题约束下，存在满足 $ f(T) < {10}^{100} $ 的 $ T $。

输入格式如下：

$ N $ $ P_1 $ $ P_2 $ $\cdots$ $ P_N $

输出答案。

部分分

• 对于满足额外条件 $ N \le 400 $ 的数据集，答对可得 $ 30 $ 分。

样例解释 1

当取 $ 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 \le N \le 5000 $
• $ 1 \le P_i \le N $
• $ P_i \ne P_j $($ i \ne j $)

由 ChatGPT 5 翻译