Foto de Grupo PSN 2016


Submit solution

Points: 100 (partial)
Time limit: 4.0s
Memory limit: 512M

Authors:
Problem type
Allowed languages
C++, Python

Descripción

Al final de la primera etapa de entrenamiento de la Preselección Nacional de Informática del 2006, se hace una foto de grupo con los N participantes. Los participantes están numerados del 1 al N, por orden de estatura. La estatura del participante h es h (1 \le h \le N).

Los participantes se colocan en las escaleras para la foto. Hay N escalones en la escalera. Los escalones están numerados del 1 al N, de un lugar más bajo a un lugar más alto.

El escalón i + 1 es más alto que el escalón i por 2 (1 \le i \le N - 1). Como los escalones de la escalera son estrechos, sólo un participante se colocará en cada escalón. Se hará una foto del grupo cuando los participantes estén alineados uno detrás de otros.

Pronto se hará una foto de grupo. Un participante se coloca en cada escalón. Ahora, el participante H_i se coloca en el escalón i (1 \le i \le N).

Sin embargo, como la diferencia de alturas de los participantes es demasiado grande, si se hace una foto con el orden actual de los participantes, algunos participantes podrían quedar ocultos detrás de otros. Por lo tanto, desea cambiar el orden de los participantes para que al menos la cabeza de cada participante aparezca en la foto. En otras En otras palabras, debe cumplirse la siguiente condición.

  • Sea a_i la altura del participante en el escalón i (1 \le i \le N). Entonces, la desigualdad a_i < a_{i+1} + 2 se satisface para cada i (1 \le i \le N - 1).

Sólo se pueden intercambiar dos participantes consecutivos. Es decir, mediante una operación, se elige un escalón i (1 \le i \le N - 1) arbitrariamente, e intercambias el participante en el escalón i y el participante en el escalón i + 1.

Quieres minimizar el número de operaciones para que se cumpla la condición anterior.

Tarea

Escribe un programa que, dado el orden de los participantes, calcule el número mínimo de operaciones

Entrada

La entrada se proporciona desde la entrada estándar en el siguiente formato. Todos los valores de entrada son enteros.

N

H_1, ...,  H_N

Salida

Escriba una línea en la salida estándar. La salida debe contener el número mínimo de operaciones.

Restriccciones

3 \le N \le 5 000.

1 \le H_i \le N (1 \le i \le N).

H_iH_j (1 \le i < j \le N).

Subtareas

  1. (5 puntos) N \le 9.
  2. (7 puntos) N \le 20.
  3. (32 puntos) N \le 200.
  4. (20 puntos) N \le 800.
  5. (36 puntos) No hay restricciones adicionales.
Ejemplos de Entrada y Salida

Ejemplo de entrada #1

5
3 5 2 4 1

Ejemplo de salida #1

3

La condición se cumple si se realizan las tres operaciones siguientes.

  • En primer lugar, intercambia los participantes en los escalones 2 y 3. Las alturas de los participantes pasan a ser 3, 2, 5, 4, 1 de un lugar más bajo a un lugar más alto.

  • En segundo lugar, se intercambian los participantes en los escalones 4 y 5. Las alturas de los participantes pasan a ser 3, 2, 5, 1, 4 de un lugar inferior a un lugar superior.

  • Por último, intercambia los participantes en los escalones 3 y 4. Las alturas de los participantes pasan a ser 3, 2, 1, 5, 4 de un lugar más bajo a un lugar más alto. Entonces se cumple la condición.

Como la condición no se cumple si realizas las operaciones menos de tres veces, la salida es 3

Ejemplo de entrada #2

5
3 2 1 5 4

Ejemplo de salida #2

0

La condición ya se cumple. No es necesario realizar ninguna operación

Ejemplo de entrada #3

9
6 1 3 4 9 5 7 8 2

Ejemplo de salida #3

9

Comments

There are no comments at the moment.