Foto de Grupo PSN 2016
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 participantes. Los participantes están numerados del al , por orden de estatura. La estatura del participante es ().
Los participantes se colocan en las escaleras para la foto. Hay escalones en la escalera. Los escalones están numerados del al , de un lugar más bajo a un lugar más alto.
El escalón es más alto que el escalón por 2 (). 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 se coloca en el escaló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 la altura del participante en el escalón (). Entonces, la desigualdad se satisface para cada ().
Sólo se pueden intercambiar dos participantes consecutivos. Es decir, mediante una operación, se elige un escalón () arbitrariamente, e intercambias el participante en el escalón y el participante en el escalón .
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.
Salida
Escriba una línea en la salida estándar. La salida debe contener el número mínimo de operaciones.
Restriccciones
• .
• ().
• ≠ ().
Subtareas
- (5 puntos) .
- (7 puntos) .
- (32 puntos) .
- (20 puntos) .
- (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 y . 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 y . 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 y . 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
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