Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito está jugando con su primita Fitiña un nuevo juego. El juego comienza con una fila con una cantidad par de cartas puestas mirando hacia arriba. En cada carta hay escrito un numero positivo. Los jugadores se alternan, Fito juega de segundo y en cada turno el jugador actual debe tomar una carta del principio o del final de la fila. Al terminar se suman las cartas que tomaron cada uno de los jugadores y el que mayor suma tenga es el ganador. Fito tiene una estrategia golosa con la que cree que le puede ganar a su primita, pero estamos intentando convencerlo de que no funciona, aunque en realidad si su primita juega de forma óptima el nunca puede ganar, o sea, a lo sumo lo mejor que puede hacer es empatar. Su estrategia consiste en tomar siempre la carta con el número más grande y en caso de que ambas sean iguales tomar la del inicio.

Para convencerlo de lo mala que es la estrategia nosotros queremos mostrarle en distintos escenarios iniciales, cuál es la mayor cantidad de puntos que le puede sacar de ventaja Fitiña si él la utiliza.

Input

La entrada consiste en varios escenarios iniciales ( a lo sumo 20 ). Cada uno se describe en una línea con un entero $N$ $(2 \le N \le 1000)$ indicando la cantidad de números en la configuración inicial, y luego los $N$ números. La última línea contiene un $0$ y no debe ser procesada. Se garantiza que los números en las cartas son siempre menores o iguales que $1000000$.

Output

Para cada caso se debe escribir: “ In game $M$, the greedy estrategy might lose by as many as $P$ points ”, donde $M$ es el número del juego y $P$ es la mayor diferencia posible entre los puntos del Fitiña y Fito, cuando este último utiliza su estrategia golosa.

Sample test(s)