Dado una lista de ~N (1 \leq N \leq 2000)~ 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.

Entrada

La primera línea de la entrada contiene un entero ~N (1 \leq N \leq 2000)~, el tamaño de la lista. En la segunda línea hay ~N~ enteros (entre 1 y ~10^9~ 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.