Subiendo y bajando por la muralla
La Gran Muralla China, Patrominio de la Humanidad por la Unesco desde 1987, es una fortificación que comenzó a construirse en el siglo V para proteger el Imperio Chino de sus enemigos del norte. Ha pasado por múltiples reconstrucciones y restauraciones a lo largo de los milenios. En 2012, el gobierno chino anunció que su longitud fue de algo menos que 21.200 kilómetros, contando todas sus ramificaciones y construcciones secundarias, aunque hoy no se conserva entera.
La Gran Muralla serpentea sobre cordilleras, por lo que recorrerla supone subir y bajar continuamente, algo que puede asfixiar a cualquiera. Los responsables del Club de Atletismo local Khala Khol quieren poner a prueba a sus socios organizando una carrera en la Gran Muralla en la que los corredores tengan que ascender lo más posible. Para eso, quieren que la salida esté en un lugar bajo, la llegada en un punto alto, y la diferencia entre esas dos posiciones sea la máxima posible.
Entrada
Cada caso de prueba comienza con un número 1 ≤ n ≤ 400.000 indicando en cuántos tramos está dividida la Gran Muralla China. En la línea siguiente aparecen n números, no mayores que 2.000 en valor absoluto, indicando el desnivel de cada tramo. Un valor positivo indica que el tramo asciende esa cantidad de metros, y un valor negativo que desciende. Los tramos aparecen en el orden en el que deben recorrerse en la carrera. Se garantiza que al menos uno es ascendente.
La entrada termina con un 0.
Salida
Por cada caso de prueba el programa escribirá la máxima diferencia posible entre la altura de la salida (que aparece antes en la entrada) y la meta.
Entrada de ejemplo
3 10 10 10 5 2 -5 8 -2 6 6 -3 3 -3 3 -3 3 3 1 -10 -10 0
Salida de ejemplo
30 12 3 1