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 $ 番目の操作では、以下の操作を行います。 > > - $ 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 $ が必ず存在することが証明できます。

入力は以下の形式で与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \cdots $ $ P_N $

答えを出力せよ。

### 部分点 - 追加の制約 $ N \le 400 $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 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 $ となります。 ### Constraints - 入力はすべて整数 - $ 2 \le N \le 5000 $ - $ 1 \le P_i \le N $ - $ P_i \ne P_j $ $ (i \ne j) $