Otro Ordenamiento

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$ ~a1, a2, \ldots, a_N~ se subdivide en $M$ ~M~ segmentos. El primer segmento incluye los números con índices desde $1$ ~1~ hasta $k_1$ ~k_1~, el segundo desde $k_1 + 1$ ~k_1 + 1~ hasta $k_2, \ldots$ ~k_2, \ldots~, el último desde $k_{M-1} + 1$ ~k_{M-1} + 1~ hasta $k_M$ ~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)$ ~N (1 \leq N \leq 500\,000)~ — la longitud de la secuencia.

La segunda línea contienen $N$ ~N~ enteros $a_i (1 \leq a_i \leq N)$ ~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$ ~M~ de segmentos de la partición.

Ejemplos

Entrada 1

6
5 6 4 3 1 2

Salida 1

Explicación

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

Entrada 2

3
1 2 1

Salida 2

Explicación

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

Comments

0

Mauricio commented on Dec. 28, 2023, 7:17 p.m.

.

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