57. Primero Último Clasificación
Autor: Desconocido
Limite de tiempo : 0.5 seg. Total runs : 5 Aceptados : 4
Dani acaba de crear una estructura de datos que realiza las dos siguientes transformaciones de la lista en tiempo O (1) constante:
• Tome cualquier elemento de la lista y muévalo al frente.
• Tome cualquier elemento de la lista y muévalo hacia atrás.
Te has dado cuenta de que la velocidad de clasificación se puede mejorar con estas transformaciones. Por ejemplo, considere la lista de entrada:
8, 3, 6, 7, 4, 1, 5, 2
Podemos hacer la siguiente secuencia de transformaciones para ordenar esta lista:
8, 3, 7, 4, 1, 5, 2, 6 (mover 6 al final)
8, 3, 4, 1, 5, 2, 6, 7 (mover 7 al final)
2, 8, 3, 4, 1, 5, 6, 7 (mover 2 al frente)
1, 2, 8, 3, 4, 5, 6, 7 (mover 1 al frente)
1, 2, 3, 4, 5, 6, 7, 8 (mover 8 hasta el final)
Ahora tienes curiosidad. Dada una matriz de entrada de valores distintos, ¿cuál es el menor número de estas primeras / últimas operaciones necesarias para clasificar la matriz?
Proporcione una permutación inicial de los dedos1, 2, ..., n, determine el número oeste de las primeras / últimas operaciones necesarias para obtener la lista de valores ordenados en orden creciente.
Entrada
La primera línea de entrada contendrá un único entero positivo, n (n ≤ 105), que representa el número de valores que se ordenarán. Las siguientes n líneas contienen un número entero cada una. Todos estos enteros serán valores distintos entre 1 y n (inclusive), que representan el orden original de los datos para ordenar para el caso de entrada.
Salida
En una línea por sí sola, genera la menor cantidad de operaciones primera / última necesaria para ordenar la lista de entrada.
Ejemplo Entrada
8
8
3
6
7
4
1
5
2
5
1
2
5
3
4
Ejemplo Salida
5
1