問題文

(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 点が与えられる。

入力例 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