On vous donne une permutation $P = (P_1, P_2, \dots, P_N)$ de $(1, 2, \dots, N)$.
Pour une suite d'entiers strictement positifs $T = (T_1, T_2, \dots, T_{N-1})$ de longueur $N - 1$, la valeur $f(T)$ est définie comme la valeur de retour de la procédure suivante.
Procédure $f(T)$
- $t \leftarrow 0$.
- Tant que $P$ n'est pas triée par ordre croissant :
- (a) $t \leftarrow t + 1$.
- (b) Soit $S = (s_1, s_2, \dots, s_k)$ la suite de tous les indices $i \in \{1, \dots, N - 1\}$ tels que $T_i \le t$, triés par ordre croissant ($s_1 < s_2 < \dots < s_k$).
- (c) Pour $j = 1$ à $k$ :
- Poser $i \leftarrow s_j$. Puis échanger $P_i$ et $P_{i+1}$.
- (d) Si $t \ge 10^{100}$, renvoyer $10^{100}$.
- Renvoyer $t$.
Trouvez la valeur minimale possible de $f(T)$ parmi toutes les suites $T$ d'entiers strictement positifs. Il est garanti qu'il existe une suite $T$ telle que $f(T) < 10^{100}$.
Entrée
L'entrée est donnée dans le format suivant :
N P_1 P_2 ... P_N
- Toutes les valeurs d'entrée sont des entiers.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ pour $i \neq j$.
Sortie
Affichez la réponse.
Exemple 1
4
4 2 1 3
2
Exemple 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Note
Dans le premier exemple, posons $T = (2, 1, 2)$. À $t = 1$, avec $S = (2)$, $P$ devient $(4, 1, 2, 3)$. À $t = 2$, avec $S = (1, 2, 3)$, les échanges successifs transforment $P$ selon $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Ainsi $f(T) = 2$. Comme aucune suite $T$ ne donne $f(T) < 2$, la réponse est $2$.