Hay ~n~ libros, y Kotivalo y Justiina van a leerlos todos. Para cada libro, saben el tiempo que tardan en leerlo.

Ambos leen cada libro de principio a fin, y no pueden leer un libro al mismo tiempo. ¿Cuál es el tiempo total mínimo necesario?

Entrada

La primera línea de entrada tiene un entero ~n~: el número de libros.

La segunda línea tiene ~n~ enteros ~t_1,t_2,\dots,t_n~: el tiempo necesario para leer cada libro.

Salida

Imprime un entero: el tiempo total mínimo.

Restricciones

• ~1 \leq n \leq 2 \cdot 10^5~
• ~1 \leq t_i \leq 10^9~

Ejemplo de Entrada

3
2 8 3

Ejemplo de Salida

16