Gegeben ist eine Permutation $P = (P_1, P_2, \dots, P_N)$ von $(1, 2, \dots, N)$.
Für eine Folge positiver ganzer Zahlen $T = (T_1, T_2, \dots, T_{N-1})$ der Länge $N - 1$ ist der Wert $f(T)$ als der Rückgabewert der folgenden Prozedur definiert.
Prozedur $f(T)$
- $t \leftarrow 0$.
- Solange $P$ nicht in aufsteigender Reihenfolge sortiert ist:
- (a) $t \leftarrow t + 1$.
- (b) Sei $S = (s_1, s_2, \dots, s_k)$ die Folge aller Indizes $i \in \{1, \dots, N - 1\}$ mit $T_i \le t$, sortiert in aufsteigender Reihenfolge ($s_1 < s_2 < \dots < s_k$).
- (c) Für $j = 1$ bis $k$:
- Setze $i \leftarrow s_j$. Vertausche dann $P_i$ und $P_{i+1}$.
- (d) Falls $t \ge 10^{100}$, gib $10^{100}$ zurück.
- Gib $t$ zurück.
Bestimme den kleinstmöglichen Wert von $f(T)$ über alle Folgen $T$ positiver ganzer Zahlen. Es ist garantiert, dass eine Folge $T$ mit $f(T) < 10^{100}$ existiert.
Eingabe
Die Eingabe erfolgt im folgenden Format:
N P_1 P_2 ... P_N
- Alle Eingabewerte sind ganze Zahlen.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ für $i \neq j$.
Ausgabe
Gib die Antwort aus.
Beispiel 1
4
4 2 1 3
2
Beispiel 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Hinweis
Im ersten Beispiel sei $T = (2, 1, 2)$. Bei $t = 1$ mit $S = (2)$ wird $P$ zu $(4, 1, 2, 3)$. Bei $t = 2$ mit $S = (1, 2, 3)$ verändern die nacheinander ausgeführten Vertauschungen $P$ gemäß $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Somit ist $f(T) = 2$. Da kein $T$ zu $f(T) < 2$ führt, lautet die Antwort $2$.