Dana jest permutacja $P = (P_1, P_2, \dots, P_N)$ ciągu $(1, 2, \dots, N)$.
Dla ciągu dodatnich liczb całkowitych $T = (T_1, T_2, \dots, T_{N-1})$ o długości $N - 1$ wartość $f(T)$ definiujemy jako wartość zwracaną przez następującą procedurę.
Procedura $f(T)$
- $t \leftarrow 0$.
- Dopóki $P$ nie jest posortowana rosnąco:
- (a) $t \leftarrow t + 1$.
- (b) Niech $S = (s_1, s_2, \dots, s_k)$ będzie ciągiem wszystkich indeksów $i \in \{1, \dots, N - 1\}$ takich, że $T_i \le t$, posortowanych rosnąco ($s_1 < s_2 < \dots < s_k$).
- (c) Dla $j = 1$ do $k$:
- Podstaw $i \leftarrow s_j$. Następnie zamień miejscami $P_i$ oraz $P_{i+1}$.
- (d) Jeśli $t \ge 10^{100}$, zwróć $10^{100}$.
- Zwróć $t$.
Znajdź minimalną możliwą wartość $f(T)$ po wszystkich ciągach dodatnich liczb całkowitych $T$. Gwarantowane jest, że istnieje ciąg $T$ taki, że $f(T) < 10^{100}$.
Wejście
Wejście podane jest w następującym formacie:
N P_1 P_2 ... P_N
- Wszystkie wartości wejściowe są liczbami całkowitymi.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ dla $i \neq j$.
Wyjście
Wypisz odpowiedź.
Przykład 1
4
4 2 1 3
2
Przykład 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Uwaga
W pierwszym przykładzie przyjmijmy $T = (2, 1, 2)$. W chwili $t = 1$, przy $S = (2)$, $P$ staje się $(4, 1, 2, 3)$. W chwili $t = 2$, przy $S = (1, 2, 3)$, kolejne zamiany zmieniają $P$ następująco: $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Zatem $f(T) = 2$. Ponieważ dla żadnego $T$ nie zachodzi $f(T) < 2$, odpowiedzią jest $2$.