Otro Ordenamiento


Submit solution

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

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

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
    Mauricio  commented on Dec. 28, 2023, 7:17 p.m.

    Concuerdo


  • 0
    legion06  commented on Aug. 4, 2023, 5:25 p.m.

    alguin me puede decir si para este problema hay que ordenar solamente de menor a mayor


  • 0
    Osvaldo23  commented on Sept. 23, 2022, 12:54 a.m.

    En caso de ser así,sustituyo cada número por el número del lugar que ocupa en la lista ya ordenada. ME parece ser una buena idea,ya sabrás porque


  • 1
    Osvaldo23  commented on Sept. 22, 2022, 4:59 p.m.

    A que se refieren con que números individuales no cambian su posición?


    • 1
      linkyless  commented on Sept. 22, 2022, 9:06 p.m.

      Hay que dividir la lista de números original en varias listas de números, para después reordenar esas listas. No movemos los números dentro de las listas, sino las listas en sí.

      PD: Con lista me refiero a array.


  • 0
    jmrh_1  commented on April 22, 2019, 3:26 p.m.

    esta muy dificil


  • 5
    jmrh_1  commented on April 22, 2019, 3:24 p.m.

    este problema es una descara