Ми визначаємо підмасив як безперервну послідовність елементів у масиві.

За даним масивом \(A\), який містить \(N\) цілих чисел, знайдіть максимально можливу суму серед всіх непорожніх підмасивів.

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

Перший рядок вхідного потоку містить ціле число \(N\) (\(1 \le N \le 10^3\))

Наступний рядок містить \(N\) цілих чисел \(A_i\) (\(-10^2 \le A_i \le 10^2\)).

Числа у рядку розділяються пропуском.

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

У вихідний потік вивести шукану суму.

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

4
1 2 3 4

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

10

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

6
2 -1 2 3 4 -5

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

10