Abanico de naipes
Mi hermano pequeño ha encontrado una baraja de cartas y está haciendo como que juega con ellas con sus amigos. Como tiene las manos pequeñas y poca práctica, le cuesta mantener en una mano una serie de cartas colocadas en forma de abanico como el de la imagen.
Cuando nos ha visto jugar se ha fijado que al coger las cartas primero las colocamos en abanico y luego las ordenamos de alguna manera, haciendo parejas o tríos, o poniendo juntas las del mismo palo. Para evitar que se le caigan todas al suelo, mi hermano ordena su abanico de cartas realizando movimientos solamente de este estilo: elige una carta, la saca del abanico y la coloca a la derecha del todo, encima de las demás.
Para practicar esta forma de ordenar, ha numerado las cartas, ha elegido al azar un conjunto de ellas, las ha colocado en forma de abanico y ha empezado a ordenarlas de manera que los números en las cartas queden ordenados de menor a mayor. Lleva un buen rato y se está empezando a poner nervioso, porque cuando ya tiene unas pocas ordenadas hace un movimiento más y se le vuelven a descolocar algunas.
Dada una configuración inicial de cartas, ¿cuál es el mínimo número de movimientos (como los que hace mi hermano, sacar una carta del abanico y colocarla a la derecha) que hay que realizar para ordenarlas de menor a mayor? Para ponertelo difícil, imaginaremos abanicos desmesuradamente grandes.
Entrada
La entrada está formada por una serie de casos de prueba. Cada caso ocupa dos líneas. En la primera apacere un número entre 1 y 100.000 que representa el número de cartas en un abanico. En la segunda línea aparecen los números escritos en cada una de esas cartas (números entre 1 y 1.000.000, todos distintos); el primer número corresponde a la carta más a la izquierda, debajo de todas, y el último a la carta más a la derecha, la que inicialmente está encima de todas.
La entrada termina con una línea con un cero, que no deberá ser procesada.
Salida
Para cada caso de prueba el programa escribirá el mínimo número de movimientos que hay que hacer para ordenar de menor a mayor los números en las cartas.
Entrada de ejemplo
4 1 2 4 3 4 9 7 5 3 3 8 9 10 0
Salida de ejemplo
1 3 0