В масиві з \(N\) чисел знайти непустий підмасив з максимальною сумою.

Формат вхідних даних

В першому рядку ціле число \(N\), кількість елементів (\(1 \le N \le 10^6\)). В наступному рядку \(N\) цілих чисел \(Ai\) - елементи масиву (\(-10000 \le Ai \le 10000\)).

Формат вихідних даних

Виведіть єдине число - максимальну суму непустого підмасиву

Приклад вхідних даних

10
2 -7 5 5 -3 5 -1 8 -100 2

Приклад вихідних даних

19