Sleepy Cow Sorting.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C#, C++, Java, JS, Pascal, Python, VB

El Granjero Juan está intentando ordenar sus N vacas (1 \leq N \leq 100), convenientemente numeradas 1...N, antes de que ellas se dirijan a los pastizales para el desayuno.

Actualmente, las vacas están en una fila en el orden p_1,p_2,p_3,...,p_N, y el Granjero Juan está parado en frente de la vaca p_1. El quiere reordenar las vacas de tal manera que estén en el orden 1,2,3,...,N, 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 k espacios abajo en la fila, para cualquier k en el rango 1...N. Las k 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 N=4 y que las vacas comienzan en el siguiente orden:

FJ: 4, 3, 2, 1

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: 3, 2, 4, 1

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 N.

La segunda línea contiene N enteros separados por espacios, p_1,p_2,p_3,...,p_N, indicando el orden inicial de las vacas.

Salida

Un solo entero, el número de pasos de tiempo antes que las N vacas estén ordenadas, si el Granjero Juan actúa óptimamente.

Ejemplo de Entrada

4
1 2 4 3

Ejemplo de Salida

3

Comments

There are no comments at the moment.