Ti viene data una permutazione $P = (P_1, P_2, \dots, P_N)$ di $(1, 2, \dots, N)$.
Per una sequenza di interi positivi $T = (T_1, T_2, \dots, T_{N-1})$ di lunghezza $N - 1$, il valore $f(T)$ è definito come il valore restituito dalla seguente procedura.
Procedura $f(T)$
- $t \leftarrow 0$.
- Finché $P$ non è ordinata in ordine crescente:
- (a) $t \leftarrow t + 1$.
- (b) Sia $S = (s_1, s_2, \dots, s_k)$ la sequenza di tutti gli indici $i \in \{1, \dots, N - 1\}$ tali che $T_i \le t$, ordinati in ordine crescente ($s_1 < s_2 < \dots < s_k$).
- (c) Per $j = 1$ fino a $k$:
- Poni $i \leftarrow s_j$. Poi scambia $P_i$ e $P_{i+1}$.
- (d) Se $t \ge 10^{100}$, restituisci $10^{100}$.
- Restituisci $t$.
Trova il minimo valore possibile di $f(T)$ su tutte le sequenze $T$ di interi positivi. È garantito che esiste una sequenza $T$ tale che $f(T) < 10^{100}$.
Input
L'input è fornito nel seguente formato:
N P_1 P_2 ... P_N
- Tutti i valori in input sono interi.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ per $i \neq j$.
Output
Stampa la risposta.
Esempio 1
4
4 2 1 3
2
Esempio 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Nota
Nel primo esempio, sia $T = (2, 1, 2)$. A $t = 1$, con $S = (2)$, $P$ diventa $(4, 1, 2, 3)$. A $t = 2$, con $S = (1, 2, 3)$, gli scambi sequenziali modificano $P$ come $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Pertanto $f(T) = 2$. Poiché nessuna $T$ dà $f(T) < 2$, la risposta è $2$.