AT_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 翻译