Gefin er umröðun $P = (P_1, P_2, \dots, P_N)$ á $(1, 2, \dots, N)$.
Fyrir runu jákvæðra heiltalna $T = (T_1, T_2, \dots, T_{N-1})$ af lengd $N - 1$ er gildið $f(T)$ skilgreint sem skilagildi eftirfarandi stefju.
Stefja $f(T)$
- $t \leftarrow 0$.
- Meðan $P$ er ekki í hækkandi röð:
- (a) $t \leftarrow t + 1$.
- (b) Látum $S = (s_1, s_2, \dots, s_k)$ vera runu allra vísa $i \in \{1, \dots, N - 1\}$ þannig að $T_i \le t$, raðaða í hækkandi röð ($s_1 < s_2 < \dots < s_k$).
- (c) Fyrir $j = 1$ upp í $k$:
- Látum $i \leftarrow s_j$. Víxlum síðan $P_i$ og $P_{i+1}$.
- (d) Ef $t \ge 10^{100}$, skilaðu $10^{100}$.
- Skilaðu $t$.
Finnið minnsta mögulega gildi $f(T)$ yfir allar runur $T$ af jákvæðum heiltölum. Það er tryggt að til sé runa $T$ þannig að $f(T) < 10^{100}$.
Inntak
Inntakið er gefið á eftirfarandi sniði:
N P_1 P_2 ... P_N
- Öll inntaksgildi eru heiltölur.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ fyrir $i \neq j$.
Úttak
Prentið svarið.
Dæmi 1
4
4 2 1 3
2
Dæmi 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Athugasemd
Í fyrsta dæminu, látum $T = (2, 1, 2)$. Við $t = 1$, með $S = (2)$, verður $P$ að $(4, 1, 2, 3)$. Við $t = 2$, með $S = (1, 2, 3)$, breyta víxlanirnar í röð $P$ sem $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Því er $f(T) = 2$. Þar sem ekkert $T$ gefur $f(T) < 2$ er svarið $2$.