Les vaches ont lancé une nouvelle activité, et Farmer John souhaite voir comment elles s’en sortent. L’activité fonctionne depuis $N$ ($1 \leq N \leq 100{,}000$) jours, et chaque jour $i$, les vaches ont enregistré leur bénéfice net $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$).

Farmer John souhaite trouver le plus grand bénéfice total obtenu par les vaches sur une période consécutive quelconque. (Notez qu’une période consécutive peut durer d’un jour à $N$ jours.) Aidez-le en écrivant un programme qui calcule la plus grande somme de bénéfices consécutifs.

Entrée

Lisez les données sur l’entrée standard.

• Ligne 1 : un seul entier, $N$.
• Lignes $2..N+1$ : la ligne $i+1$ contient un seul entier, $P_i$.

Sortie

Écrivez le résultat sur la sortie standard.

• Ligne 1 : un seul entier représentant la somme maximale de bénéfices sur une période consécutive quelconque.

Exemples

Entrée 1

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

Sortie 1

14

Remarque

La somme maximale est obtenue en additionnant les nombres du deuxième au sixième (4, 9, -2, -5, 8), ce qui donne 14.

Auteur du problème : Neal Wu, 2007