As vacas abriram um novo negócio e Farmer John quer saber como estão a correr as coisas. O negócio funciona há $N$ ($1 \leq N \leq 100{,}000$) dias e, em cada dia $i$, as vacas registaram o seu lucro líquido $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$).

Farmer John quer encontrar o maior lucro total que as vacas obtiveram durante qualquer período consecutivo. (Note que um período consecutivo pode durar de um dia a $N$ dias.) Ajude-o escrevendo um programa que calcule a maior soma de lucros consecutivos.

Entrada

Leia a entrada a partir da entrada padrão.

• Linha 1: um único inteiro, $N$.
• Linhas $2..N+1$: a linha $i+1$ contém um único inteiro, $P_i$.

Saída

Escreva a saída na saída padrão.

• Linha 1: um único inteiro que representa a soma máxima de lucros em qualquer período consecutivo.

Exemplos

Entrada 1

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

Saída 1

14

Nota

A soma máxima obtém-se somando do segundo ao sexto número (4, 9, -2, -5, 8), resultando em 14.

Autor do problema: Neal Wu, 2007