$(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)$ を次の手続きの戻り値として定義します。
手続き $f(T)$
- $t \leftarrow 0$。
- $P$ が昇順にソートされていない間、以下を繰り返す:
- (a) $t \leftarrow t + 1$。
- (b) $T_i \le t$ を満たすすべての添字 $i \in \{1, \dots, N - 1\}$ を昇順に並べた列を $S = (s_1, s_2, \dots, s_k)$ とする($s_1 < s_2 < \dots < s_k$)。
- (c) $j = 1$ から $k$ まで順に以下を行う:
- $i \leftarrow s_j$ とおく。その後、$P_i$ と $P_{i+1}$ を交換する。
- (d) もし $t \ge 10^{100}$ ならば、$10^{100}$ を返す。
- $t$ を返す。
すべての正の整数列 $T$ にわたる $f(T)$ の最小値を求めてください。$f(T) < 10^{100}$ となる列 $T$ が存在することが保証されます。
入力
入力は以下の形式で与えられます。
N P_1 P_2 ... P_N
- 入力される値はすべて整数である。
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $i \neq j$ のとき $P_i \neq P_j$。
出力
答えを出力してください。
入力例 1
4
4 2 1 3
2
入力例 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
注記
1つ目の例では、$T = (2, 1, 2)$ とします。$t = 1$ のとき、$S = (2)$ より $P$ は $(4, 1, 2, 3)$ になります。$t = 2$ のとき、$S = (1, 2, 3)$ より順次交換を行うことで $P$ は $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$ と変化します。したがって $f(T) = 2$ です。$f(T) < 2$ となる $T$ は存在しないため、答えは $2$ です。