Die Kühe haben ein neues Geschäft eröffnet, und Farmer John möchte sehen, wie gut es läuft. Das Geschäft besteht seit $N$ ($1 \leq N \leq 100{,}000$) Tagen, und jeden Tag $i$ haben die Kühe ihren Nettogewinn $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$) aufgezeichnet.

Farmer John möchte den größten Gesamtgewinn finden, den die Kühe in irgendeinem zusammenhängenden Zeitraum erzielt haben. (Beachte, dass ein zusammenhängender Zeitraum zwischen einem Tag und $N$ Tagen lang sein kann.) Hilf ihm, indem du ein Programm zur Berechnung der größten Summe aufeinanderfolgender Gewinne schreibst.

Eingabe

Lies die Eingabe von der Standardeingabe.

• Zeile 1: eine einzelne ganze Zahl $N$.
• Zeilen $2..N+1$: Zeile $i+1$ enthält eine einzelne ganze Zahl $P_i$.

Ausgabe

Schreibe die Ausgabe auf die Standardausgabe.

• Zeile 1: eine einzelne ganze Zahl, die die maximale Gewinnsumme für irgendeinen zusammenhängenden Zeitraum angibt.

Beispiele

Eingabe 1

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

Ausgabe 1

14

Hinweis

Die maximale Summe ergibt sich aus den Zahlen von der zweiten bis zur sechsten (4, 9, -2, -5, 8) und beträgt 14.

Autor der Aufgabe: Neal Wu, 2007