Problem
Cuando se juega un juego nuevo (un híbrido de bolos y billar), se usan N bolas, numeradas del 1 al N. Al comienzo del juego, estas bolas deben colocarse en una línea en orden numérico. Durante el juego, su orden puede cambiar.
Para organizar las bolas antes del comienzo del próximo juego, se utiliza el siguiente dispositivo. Este dispositivo consta de una cabeza que, moviéndose sobre las bolas, puede "chupar" y "escupir" globos Para tener una mejor idea de este dispositivo, imagine una aspiradora que pueda aspirar bolas, muévase al lugar correcto y allí, soplando en la dirección opuesta, "escupe" las bolas.
Cuando se succiona un globo, todos los globos que estaban a la derecha del succionado se desplazan hacia la izquierda. "Escupir" la bola puede estar entre dos bolas cualesquiera (y también antes de la primera bola o después de la última), luego la bola que escupe se inserta entre estas bolas, y todas las bolas que están a la derecha de la insertada se desplazan a la derecha .
El dispositivo puede succionar más de una bola al mismo tiempo y, al escupir la bola, la última bola succionada se escupe primero, luego la penúltima, y así sucesivamente. (es decir, el dispositivo funciona según el principio de una pila). Las bolas se escupen una a la vez, es decir, puedes escupir solo una bola, dejando el resto dentro del dispositivo (en este caso, puedes seguir “escupir” las bolas en el mismo lugar o en otro, o succionar nuevas bolas).
La operación que consume más energía de las descritas es la operación de chupar la pelota, por lo que queremos minimizar el número de tales operaciones.
Escriba un programa que, dada la disposición inicial de las bolas, determine el número mínimo de succiones requeridas para colocar las bolas en orden numérico.
Entrada
En el archivo de entrada, el número N se da primero — número de bolas (1≤N≤1000). Luego, hay N números que dan los números de las bolas en orden de izquierda a derecha en su ubicación actual (cada número, del 1 al N, y cada uno de los números aparece exactamente una vez en la secuencia).
Salida
Producir un solo número — el número mínimo de operaciones de succión de bolas que se requerirán para colocar las bolas en el orden de sus números.
Comentarios sobre pruebas de muestra
1.Puedes chupar, por ejemplo, el globo número 2 y escupirlo entre el 1er y el 3er globo.
2.>Puedes hacer algo como esto. Primero,
chupe el globo número 1, luego – bola número 2. Luego nos movemos al principio y escupimos la bola antes de la cuarta bola (esta será la bola número 2). A continuación, succione el globo número 3 y escúpalo entre los globos 2 y 4. Luego muévase al principio y escupa allí el globo número 1. Sin embargo, este no es el único orden posible de los globos en este ejemplo.
| Entrada |
Salida |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
Olimpiada por equipos, Olimpiada por equipos de Moscú, grados 9-11, 2007, Liga A, Problema F