Дано масив \(A\) з \(N\) цілих чисел.

Знайдіть суміжний підмасив (що містить принаймні одне число), який має максимальну суму.

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

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

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

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

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

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

Обмеження:

• \(1 ≤ N ≤ 10^6\)
• \(-10^7 ≤ A_i ≤ 10^7\)

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

5
1 2 3 -2 5

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

9

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

4
-1 -2 -3 -4

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

-1