Du får oppgitt en permutasjon $P = (P_1, P_2, \dots, P_N)$ av $(1, 2, \dots, N)$.
For en følge av positive heltall $T = (T_1, T_2, \dots, T_{N-1})$ med lengde $N - 1$, er verdien $f(T)$ definert som returverdien til følgende prosedyre.
Prosedyre $f(T)$
- $t \leftarrow 0$.
- Så lenge $P$ ikke er sortert i stigende rekkefølge:
- (a) $t \leftarrow t + 1$.
- (b) La $S = (s_1, s_2, \dots, s_k)$ være følgen av alle indekser $i \in \{1, \dots, N - 1\}$ slik at $T_i \le t$, sortert i stigende rekkefølge ($s_1 < s_2 < \dots < s_k$).
- (c) For $j = 1$ til $k$:
- La $i \leftarrow s_j$. Bytt deretter $P_i$ og $P_{i+1}$.
- (d) Hvis $t \ge 10^{100}$, returner $10^{100}$.
- Returner $t$.
Finn den minste mulige verdien av $f(T)$ over alle følger $T$ av positive heltall. Det er garantert at det finnes en følge $T$ slik at $f(T) < 10^{100}$.
Inndata
Inndataene er gitt i følgende format:
N P_1 P_2 ... P_N
- Alle inndataverdier er heltall.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ for $i \neq j$.
Utdata
Skriv ut svaret.
Eksempel 1
4
4 2 1 3
2
Eksempel 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Merknad
I det første eksempelet, la $T = (2, 1, 2)$. Ved $t = 1$, med $S = (2)$, blir $P$ til $(4, 1, 2, 3)$. Ved $t = 2$, med $S = (1, 2, 3)$, endrer sekvensielle bytter $P$ som $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Dermed er $f(T) = 2$. Siden ingen $T$ gir $f(T) < 2$, er svaret $2$.