Se te da una permutación $P = (P_1, P_2, \dots, P_N)$ de $(1, 2, \dots, N)$.
Para una sucesión de enteros positivos $T = (T_1, T_2, \dots, T_{N-1})$ de longitud $N - 1$, el valor $f(T)$ se define como el valor de retorno del siguiente procedimiento.
Procedimiento $f(T)$
- $t \leftarrow 0$.
- Mientras $P$ no esté ordenada en orden ascendente:
- (a) $t \leftarrow t + 1$.
- (b) Sea $S = (s_1, s_2, \dots, s_k)$ la sucesión de todos los índices $i \in \{1, \dots, N - 1\}$ tales que $T_i \le t$, ordenados en orden creciente ($s_1 < s_2 < \dots < s_k$).
- (c) Para $j = 1$ hasta $k$:
- Sea $i \leftarrow s_j$. Luego intercambia $P_i$ y $P_{i+1}$.
- (d) Si $t \ge 10^{100}$, devuelve $10^{100}$.
- Devuelve $t$.
Encuentra el valor mínimo posible de $f(T)$ entre todas las sucesiones $T$ de enteros positivos. Se garantiza que existe una sucesión $T$ tal que $f(T) < 10^{100}$.
Entrada
La entrada se proporciona en el siguiente formato:
N P_1 P_2 ... P_N
- Todos los valores de entrada son enteros.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ para $i \neq j$.
Salida
Imprime la respuesta.
Ejemplo 1
4
4 2 1 3
2
Ejemplo 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Nota
En el primer ejemplo, sea $T = (2, 1, 2)$. En $t = 1$, con $S = (2)$, $P$ se convierte en $(4, 1, 2, 3)$. En $t = 2$, con $S = (1, 2, 3)$, los intercambios secuenciales cambian $P$ como $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Así, $f(T) = 2$. Como ningún $T$ produce $f(T) < 2$, la respuesta es $2$.