Krowy otworzyły nową działalność, a Farmer John chce sprawdzić, jak sobie radzą. Działalność trwa już $N$ ($1 \leq N \leq 100{,}000$) dni, a każdego dnia $i$ krowy zapisywały swój zysk netto $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$).

Farmer John chce znaleźć największy łączny zysk uzyskany przez krowy w dowolnym ciągłym okresie. (Zauważ, że ciągły okres może trwać od jednego dnia do $N$ dni.) Pomóż mu, pisząc program obliczający największą sumę kolejnych zysków.

Wejście

Czytaj dane ze standardowego wejścia.

• Wiersz 1: jedna liczba całkowita $N$.
• Wiersze $2..N+1$: wiersz $i+1$ zawiera jedną liczbę całkowitą $P_i$.

Wyjście

Zapisz wynik na standardowe wyjście.

• Wiersz 1: jedna liczba całkowita oznaczająca największą sumę zysków w dowolnym ciągłym okresie.

Przykład

Wejście 1

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

Wyjście 1

14

Uwagi

Największą sumę uzyskuje się, sumując liczby od drugiej do szóstej (4, 9, -2, -5, 8); wynosi ona 14.

Autor zadania: Neal Wu, 2007