Las vacas pensantes
Los humanos no tienen ni idea de en qué pensamos las vacas. Nos veis descansando a la sombra de un árbol, sin preocuparnos de los problemas del mundo y suponéis que no tenemos nada entre oreja y oreja. Pero estáis equivocados, pensamos mucho en los problemas que nos importan, como cuándo será la siguiente comida.
A mi jefe, el granjero Sancho, le gusta ponernos retos. Antes de ordeñarnos, coloca una hilera de cubos con diferentes cantidades de comida y elige dos vacas. Estas deben alternarse para comer y cada una, en su turno, debe elegir uno de los cubos de los extremos, comerse su contenido y retirarlo. Así hasta que se acaban los cubos.
Cuando me emparejan con mi compañera Devoradora ella siempre sigue la misma estrategia: comer el cubo de los extremos que tenga mayor cantidad. Yo solía elegir al azar, pero con ella suelo quedarme hambrienta. Y aunque el hambre puede sacar lo mejor de nosotros, no quiero que vuelva a ocurrir. ¿Puedes ayudarme a calcular cuánto puedo comer como máximo si me toca empezar a comer y me enfrento a Devoradora?
Entrada
La entrada estará compuesta por varios casos de prueba, cada uno ocupando dos líneas. La primera línea contiene el número N (entre 1 y 1.000) de cubos. La segunda línea contiene N enteros diferentes entre 1 y 10.000, que representan las cantidades de comida en los N cubos según están colocados de izquierda a derecha.
La entrada termina con un caso sin cubos, que no debe procesarse.
Salida
Para cada caso de prueba se escribirá una línea con la cantidad máxima que puede comer nuestra amiga si le toca empezar a comer y se enfrenta a Devoradora.
Entrada de ejemplo
4 8 7 1 4 4 2 4 15 5 7 6 11 3 15 9 4 12 0
Salida de ejemplo
12 17 35