Sleepy Cow Sorting.
El Granjero Juan está intentando ordenar sus N vacas , convenientemente numeradas , antes de que ellas se dirijan a los pastizales para el desayuno.
Actualmente, las vacas están en una fila en el orden , y el Granjero Juan está parado en frente de la vaca . El quiere reordenar las vacas de tal manera que estén en el orden , con la vaca 1 al lado del Granjero Juan.
Hoy día las vacas están algo dormidas, por lo tanto en cualquier momento la única vaca que está prestando atención a las instrucciones del Granjero Juan es la vaca que está mirando directamente al Granjero Juan. En un paso de tiempo, él puede instruir a esta vaca a moverse espacios abajo en la fila, para cualquier en el rango . Las vacas que ella pasa se correrán hacia adelante, haciendo espacio para que ella se inserte en la fila después de ellas.
Por ejemplo, suponga que y que las vacas comienzan en el siguiente orden:
FJ:
La única vaca que le está prestando atención a GJ es la vaca 4. Si él la instruye a moverse 2 espacios en la fila, el orden se verá después como esto:
FJ:
Ahora la única vaca que le está prestando atención a GJ es la vaca 3, entonces en el segundo paso de tiempo él puede dar a la vaca 3 una instrucción, y así sucesivamente hasta que las vacas estén ordenadas.
El Granjero Juan tiene afán en completar el ordenamiento, así el puede regresar a la casa para desayunar. Ayúdelo a encontrar el número mínimo de pasos de tiempo necesarios para ordenar las vacas.
Entrada
La primera línea de la entrada contiene .
La segunda línea contiene enteros separados por espacios, , indicando el orden inicial de las vacas.
Salida
Un solo entero, el número de pasos de tiempo antes que las vacas estén ordenadas, si el Granjero Juan actúa óptimamente.
Ejemplo de Entrada
4
1 2 4 3
Ejemplo de Salida
3
Comments