Ordenando - I
Dado una lista de números (enteros positivos) se desea ordenarlos en forma no decreciente. La única operación permitida para ordenar los números es seleccionar un elemento y moverlo a otro lugar en la lista. Se puede mover un elemento al principio o al final de la lista, así como ubicarlo entre dos elementos consecutivos. El costo de una operación es igual al valor del elemento movido. Se quiere que escribas un programa para minimizar el costo de ordenar los números en la lista.
Entrada
La primera línea de la entrada contiene un entero , el tamaño de la lista. En la segunda línea hay enteros (entre 1 y inclusive) separados por espacios describiendo los elementos en la lista.
Salida
La salida consta de un único entero: el menor costo para ordenar la lista.
Entrada #1
4
7 1 2 3
Salida #1
6
Entrada #2
4
7 1 2 5
Salida #2
7
Entrada #3
6
8 2 6 5 1 4
Salida #3
18
Hint
Utilice enteros de 64 bits para los cálculus.
Comments