Dado un arreglo de ~n~ números, tu tarea es dividirlo en ~n~ subarreglos, cada uno con un solo elemento. En cada turno, puedes elegir cualquier subarreglo y dividirlo en dos. El costo de cada turno es la suma de los valores en el subarreglo elegido.

¿Cuál es el costo total mínimo si operas de forma óptima?

Entrada

• La primera línea de entrada contiene un entero ~n~: el tamaño del arreglo. Los elementos del arreglo están numerados del ~1,2,\dots,n.~.
• La segunda línea contiene ~n~ enteros ~x_1,x_2,\dots,x_n~: los elementos del arreglo.

Salida

Imprime un entero: el costo total mínimo.

Restricciones

• ~1 \le n \le 5000~
• ~1 \le x_i \le 10^9~

Ejemplo de Entrada

5
2 7 3 2 5

Ejemplo de Salida

43