Hay una vara plegable formada por $n$ segmentos de longitud positiva. Los segmentos están conectados mediante bisagras (cuerdas elásticas), que permiten plegarlos 180 grados en cada bisagra. Se llama longitud de embalaje a la longitud de la vara después de plegarla en una o más bisagras. Esta longitud puede variar según la estrategia de plegado.

Debes encontrar la longitud mínima de embalaje bajo la condición de que la vara se pliegue de la siguiente manera: primero coloca los segmentos a lo largo de una línea horizontal. Después pliega la vara en sentido horario, de izquierda a derecha. Durante el plegado, el segmento unido al lado izquierdo de cada bisagra gira 180 grados en sentido horario o no gira en absoluto.

Por ejemplo, la figura siguiente muestra una vara de cuatro segmentos cuya suma de longitudes es $10$. Las longitudes, de izquierda a derecha, son $3,2,2,3$, y las bisagras están marcadas como ①, ② y ③.

En este ejemplo, la vara no se puede plegar tanto en la bisagra ① como en la ②. Si se pliega en ① y después en ②, el segmento de longitud $3$ que pasa sobre la bisagra ② se romperá. Si se pliega solo en ②, la longitud de embalaje es $5$. Si se pliega en ① y ③ en ese orden, la longitud de embalaje es $4$, como en la figura siguiente.

Dada una secuencia de longitudes de los segmentos de una vara plegable, escribe un programa que imprima su longitud mínima de embalaje.

Entrada

Tu programa debe leer de la entrada estándar. La entrada empieza con una línea que contiene un entero $n$ ($2\le n\le100000$), el número de segmentos de la vara. La siguiente línea contiene $n$ enteros positivos que representan las longitudes de los segmentos desde el extremo izquierdo hasta el derecho. La longitud de cada segmento no supera $20000$.

Salida

Tu programa debe escribir en la salida estándar. Imprime exactamente una línea que contenga el entero positivo que representa la longitud mínima de embalaje.

A continuación se muestra la entrada y la salida de ejemplo para tres casos de prueba.

Ejemplos

Entrada 1

4
3 2 2 3

Salida 1

4

Entrada 2

5
1 1 1 1 1

Salida 2

1

Entrada 3

7
1 3 2 3 4 2 2

Salida 3

6