Contando en sort de Inserción

Time Limit:
1 Sec
Memory Limit:
128Mb
Enviados:
606
Resuelto:
322

Descripción

Una secuencia de números distintos va a ser ordenada utilizando el método de ordenación por inserción.
La ordenación por inserción funciona como sigue:


insertion-sort(A)
   inicializar una nueva secuencia vacía R
   para cada numero N en A en el orden original hacer:
      determinar el índice donde i en R debe ser insertado,
          para que R permanezca ordenado
          mueva cada elemento en R con un índice 
                  mayor o igual a i 
                  al índice siguiente para hacer un espacio
                  ponga R[i]=N
   El vector R esta ordenado



por ejemplo una ordenación por inserción del vector {20,40,30,10} producirá los siguientes estados para R.


  • El primer elemento (índice 0) es R={20}
  • Insertar 40 no requiere movimientos R={20,40}
  • Insertar el próximo elemento requiere que el 40 se mueva un lugar R={20,30,40}
  • El 10 debe insertarse en la posicion 0 haciendo que se recorran los elementos siguientes, para obtener finalmente el vector ordenado R={10,20,30,40}



¿ Cuantos elementos se movieron?. Para insertar el 30 movimos el 40 una vez, para insertar el 10 tuvimos que mover el 20, 30 y 40, haciendo un total de 4 movimientos.

Dado un vector de números escribir una línea con el número de movimientos necesarios para ordenar el vector.

Entrada

Los datos de entrada consisten de múltiples casos de prueba. Cada caso de prueba es un vector con 1 <= n <= 50 números, que están en una línea, separados por un espacio. La entrada termina cuando no hay mas datos.

Salida

Por cada caso de prueba escriba una línea con la cantidad de movimientos necesarios para ordenar el vector utilizando en método descrito.

Ejemplo Entrada

Copy icon
20 40 30 10
-1 1 0
-1000 0 1000

Ejemplo Salida

Copy icon
4
1
0

Ayuda

crear un vector y realiza insercion sort, de esto por cada movimiento al insertar debera ser contado