Las vacas han abierto un nuevo negocio y Farmer John quiere ver cómo les va. El negocio lleva funcionando $N$ ($1 \leq N \leq 100{,}000$) días, y cada día $i$ las vacas han registrado su beneficio neto $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$).

Farmer John quiere encontrar el mayor beneficio total que han obtenido las vacas durante cualquier periodo consecutivo. (Ten en cuenta que un periodo consecutivo puede durar desde un día hasta $N$ días.) Ayúdalo escribiendo un programa que calcule la mayor suma de beneficios consecutivos.

Entrada

Lee la entrada desde la entrada estándar.

• Línea 1: un único entero, $N$.
• Líneas $2..N+1$: la línea $i+1$ contiene un único entero, $P_i$.

Salida

Escribe la salida en la salida estándar.

• Línea 1: un único entero que representa la suma máxima de beneficios en cualquier periodo consecutivo.

Ejemplos

Entrada 1

7
-3
4
9
-2
-5
8
-3

Salida 1

14

Nota

La suma máxima se obtiene sumando desde el segundo hasta el sexto número (4, 9, -2, -5, 8), lo que da 14.

Autor del problema: Neal Wu, 2007