A AlanashKO le encanta el dinero. En vísperas de Año Nuevo le regalaron $N$ billetes. El valor nominal de cada billete es un entero positivo. Mientras jugaba, AlanashKO colocó todos los billetes en una fila y los numeró de izquierda a derecha del $1$ al $N$. Después decidió ordenar todos los billetes en orden no decreciente. Para ello, AlanashKO realiza el siguiente procedimiento: primero divide los billetes en uno o varios subsegmentos disjuntos, de modo que cada billete pertenece a algún subsegmento. A continuación, inserta todos los subsegmentos, por turnos y en su orden de izquierda a derecha, en una fila nueva; es decir, primero inserta el subsegmento situado más a la izquierda (el primer subsegmento), luego el siguiente situado más a la izquierda, y así sucesivamente. Cada subsegmento se inserta entre dos billetes cualesquiera o en uno de los dos extremos de la fila nueva actual. Al insertarlo, no cambia el orden de los billetes dentro del subsegmento.
AlanashKO quiere minimizar el número de subsegmentos que le permita finalmente ordenar los billetes en orden no decreciente. Ayúdalo a encontrar este valor.
Entrada
La primera línea contiene un único entero positivo $N$ ($1 \le N \le 10^6$): el número de billetes. La siguiente línea contiene $N$ enteros positivos $a_i$ ($1 \le a_i \le 10^6$): el valor del $i$-ésimo billete.
Salida
En una única línea, imprime un solo entero: el número mínimo de subsegmentos que permite a AlanashKO ordenar los billetes.
Subtareas
Esta tarea incluye cuatro subtareas:
- $N \le 8$. Puntuación: 9 puntos.
- $N \le 20$. Puntuación: 16 puntos.
- $N \le 300$. Puntuación: 20 puntos.
- $N \le 10^6$. Puntuación: 55 puntos.
Cada subtarea solo se puntuará si la solución supera correctamente todas las subtareas anteriores.
Ejemplos
Entrada 1
6 3 6 4 5 1 2
Salida 1
3
Nota
Un subsegmento es una secuencia de elementos consecutivos.
Consideremos el caso de ejemplo:
La respuesta mínima corresponde a dividir en 3 subsegmentos: |3 6|4 5|1 2| (las barras marcan los límites de los subsegmentos).
Después del primer paso: la fila inicial es |4 5|1 2| y la fila nueva es |3 6|.
En el segundo paso se inserta el subsegmento |4 5| entre $3$ y $6$.
Después del segundo paso: la fila inicial es |1 2| y la fila nueva es |3 4 5 6|.
Finalmente se inserta el subsegmento |1 2| al principio de la fila nueva y se obtiene |1 2 3 4 5 6|.