Otro Ordenamiento

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type

Los alumnos de la Preselección de Informática de IslaGrande están muy motivados por el nuevo método de ordenamiento aprendido.

La esencia de este método es muy simple: una secuencia de números \(a1, a2, \ldots, a_N\) se subdivide en \(M\) segmentos. El primer segmento incluye los números con índices desde \(1\) hasta \(k_1\), el segundo desde \(k_1 + 1\) hasta \(k_2, \ldots\), el último desde \(k_{M-1} + 1\) hasta \(k_M\). Adicionalmente, en el proceso de ordenamiento, números individuales no cambian de posición, solamente los segmentos serán reordenados.

Para hacer este método de ordenamiento fácil de entender, el entrenador les asignó a los alumnos una tarea: dividir la secuencia en el mínimo número de segmentos tal que sea posible aplicar al segmento el método de ordenamiento.

Usted, uno de los estudiantes más entusiastas, decidió escribir un programa que le permita resolver el problema para cualquier secuencia de números.

Entrada

La primera línea de entrada contiene un entero \(N (1 \leq N \leq 500\,000)\) — la longitud de la secuencia.

La segunda línea contienen \(N\) enteros \(a_i (1 \leq a_i \leq N)\) — los elementos de la secuencia.

Los números en línea están separados por un espacio.

Salida

La única línea debe contener el mínimo número \(M\) de segmentos de la partición.

Ejemplos

Entrada 1
6
5 6 4 3 1 2
Salida 1
4
Explicación

La secuencia puede dividirse en cuatro segmentos \((5 6), (4), (3) y (1 2)\). El segmento \((1 2)\) debe colocarse primero, \((3)\) segundo, \((4)\) tercero y \((5 6)\) último. Así la secuencia puede ordenarse.

Entrada 2
3
1 2 1
Salida 2
2
Explicación

La secuencia original puede dividirse en los segmentos \((1 2)\) y \((1)\).


Comments


  • 1
    jmrh_1  commented on April 22, 2019, 11:26 a.m.

    esta muy dificil


  • 2
    jmrh_1  commented on April 22, 2019, 11:24 a.m.

    este problema es una descara