Du får en permutation $P = (P_1, P_2, \dots, P_N)$ av $(1, 2, \dots, N)$.
För en följd av positiva heltal $T = (T_1, T_2, \dots, T_{N-1})$ av längd $N - 1$ definieras värdet $f(T)$ som returvärdet från följande procedur.
Procedur $f(T)$
- $t \leftarrow 0$.
- Så länge $P$ inte är sorterad i stigande ordning:
- (a) $t \leftarrow t + 1$.
- (b) Låt $S = (s_1, s_2, \dots, s_k)$ vara följden av alla index $i \in \{1, \dots, N - 1\}$ sådana att $T_i \le t$, sorterade i stigande ordning ($s_1 < s_2 < \dots < s_k$).
- (c) För $j = 1$ till $k$:
- Låt $i \leftarrow s_j$. Byt sedan plats på $P_i$ och $P_{i+1}$.
- (d) Om $t \ge 10^{100}$, returnera $10^{100}$.
- Returnera $t$.
Bestäm det minsta möjliga värdet på $f(T)$ över alla följder $T$ av positiva heltal. Det garanteras att det finns en följd $T$ sådan att $f(T) < 10^{100}$.
Indata
Indatan ges i följande format:
N P_1 P_2 ... P_N
- Alla indatavärden är heltal.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ för $i \neq j$.
Utdata
Skriv ut svaret.
Exempel 1
4
4 2 1 3
2
Exempel 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Anmärkning
I det första exemplet, låt $T = (2, 1, 2)$. Vid $t = 1$, med $S = (2)$, blir $P$ lika med $(4, 1, 2, 3)$. Vid $t = 2$, med $S = (1, 2, 3)$, ändrar de sekventiella bytena $P$ enligt $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Alltså är $f(T) = 2$. Eftersom inget $T$ ger $f(T) < 2$ är svaret $2$.