Sinulle annetaan lukujen $(1, 2, \dots, N)$ permutaatio $P = (P_1, P_2, \dots, P_N)$.
Positiivisten kokonaislukujen jonolle $T = (T_1, T_2, \dots, T_{N-1})$, jonka pituus on $N - 1$, arvo $f(T)$ määritellään seuraavan proseduurin paluuarvoksi.
Proseduuri $f(T)$
- $t \leftarrow 0$.
- Niin kauan kuin $P$ ei ole järjestetty nousevaan järjestykseen:
- (a) $t \leftarrow t + 1$.
- (b) Olkoon $S = (s_1, s_2, \dots, s_k)$ kaikkien sellaisten indeksien $i \in \{1, \dots, N - 1\}$ jono, joilla $T_i \le t$, järjestettynä nousevaan järjestykseen ($s_1 < s_2 < \dots < s_k$).
- (c) Käydään läpi $j = 1$:stä $k$:hon:
- Asetetaan $i \leftarrow s_j$. Vaihdetaan sitten $P_i$ ja $P_{i+1}$ keskenään.
- (d) Jos $t \ge 10^{100}$, palauta $10^{100}$.
- Palauta $t$.
Etsi pienin mahdollinen arvo $f(T)$ yli kaikkien positiivisten kokonaislukujen jonojen $T$. On taattu, että on olemassa jono $T$, jolle $f(T) < 10^{100}$.
Syöte
Syöte annetaan seuraavassa muodossa:
N P_1 P_2 ... P_N
- Kaikki syötteen arvot ovat kokonaislukuja.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$, kun $i \neq j$.
Tuloste
Tulosta vastaus.
Esimerkki 1
4
4 2 1 3
2
Esimerkki 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Huomautus
Ensimmäisessä esimerkissä olkoon $T = (2, 1, 2)$. Kun $t = 1$ ja $S = (2)$, $P$:stä tulee $(4, 1, 2, 3)$. Kun $t = 2$ ja $S = (1, 2, 3)$, peräkkäiset vaihdot muuttavat $P$:tä seuraavasti: $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Siis $f(T) = 2$. Koska mikään $T$ ei tuota tulosta $f(T) < 2$, vastaus on $2$.