¡Bessie y Bonnie han encontrado un Cofre de Tesoros lleno de maravillosas monedas de oro! Sin embargo, siendo vacas, ellas no pueden caminar simplemente a una tienda y comprar cosas. En vez de esto, ellas deciden divertirse con las monedas.

Las ~N (1 \leq N \leq 5,000)~ monedas, cada una con algún valor ~C_i (1 \leq C_i \leq 5,000)~ son colocadas en una línea recta. Bessie y Bonnie juegan por turnos, y en cada turno, la jugadora que tiene el turno toma exactamente una moneda o del extremo izquierdo o del extremo derecho de la línea. El juego termina cuando no quedan monedas.

Tanto Bessie como Bonnie quieren obtener tanta ganancia como sea posible para ellas mismas. Bessie va primero. Ayúdela a saber el valor máximo que ella puede ganar, asumiendo que ambas vacas juegan de manera óptima.

Considere un juego en el cual están alineadas cuatro monedas con estos valores:

 30 25 10 35

Considere esta secuencia de juego:

                                  Total    Total       Nueva línea
Jugadora  Lado      ValorMoneda  Bessie    Bonnie       de monedas
Bessie    Derecho      35         35         0         30  25  10
Bonnie    Izquierdo    30         35        30           25  10
Bessie    Izquierdo    25         60        30             10
Bonnie    Derecho      10         60        40             --

Esto es lo mejor que puede hacer Bessie.

Entrada

• Línea 1: Un solo entero: ~N~

• Líneas 2..N+1: La línea i+1 contiene un solo entero: ~C_i~

Ejemplo de Entrada

4
30
25
10
35

Salida

• Línea 1: Un solo entero, el cual el valor total mas grande que Bessie puede ganar si ambas vacas juegan óptimamente.

Ejemplo de Salida

60