俾一個 $(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) 設 $S = (s_1, s_2, \dots, s_k)$ 為所有滿足 $T_i \le t$ 嘅下標 $i \in \{1, \dots, N - 1\}$ 按升序排列組成嘅序列(即 $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)$ 嘅最小可能值。保證存在一個序列 $T$ 令到 $f(T) < 10^{100}$。
輸入格式
輸入按以下格式俾出:
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
樣例說明
喺第一個樣例入面,設 $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$。因為唔存在任何 $T$ 令到 $f(T) < 2$,所以答案係 $2$。