Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Dado una lista de N ( 1 <= N <= 200000 ) 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 números en la lista.

Input

La primera línea de la entrada contiene un entero N (1 <= N <= 2 * 10 ⁵ ), el tamaño de la lista. En la segunda línea hay N enteros (entre 1 y 10 ⁹ inclusive) separados por espacios describiendo los elementos en la lista.

Output

La salida consta de un único entero: el menor costo para ordenar la lista.

Sample test(s)

Hints

Hints
Utilice enteros de 64 bits para los cálculos.