Hay una lista de ~n~ números y dos jugadores que se mueven alternativamente. En cada movimiento, un jugador elimina el primer o el último número de la lista, y su puntuación aumenta en ese número. Ambos jugadores intentan maximizar sus puntuaciones.

¿Cuál es la máxima puntuación posible para el primer jugador cuando ambos juegan de forma óptima?

Entrada

La primera línea de entrada contiene un número entero ~n~: el tamaño de la lista.

La siguiente línea tiene ~n~ enteros ~x_1,x_2,\ldots,x_n~: el contenido de la lista.

Salida

Imprime la máxima puntuación posible para el primer jugador.

Restricciones

• ~1 \leq n \leq 5000~.
• ~-10^9 \leq x_i \leq 10^9~.

Ejemplo de Entrada

4
4 5 1 3

Ejemplo de Salida

8