Вам задано послідовність з ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~.

Відрізком (неперервним підмасивом) називається будь-яка непорожня послідовність підряд йдучих елементів ~a_l, a_{l+1}, \ldots, a_r~, де ~1 \le l \le r \le n~.

Знайдіть максимальну можливу суму елементів одного відрізка.

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

Вхідні дані

• Перший рядок містить одне ціле число ~n~ (~1 \le n \le 2 \cdot 10^5~).
• Другий рядок містить ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~).

Вихідні дані

Виведіть одне ціле число — максимальну суму непорожнього відрізка.

Приклади

Приклад 1

Вхідні дані:

9
-2 1 -3 4 -1 2 1 -5 4

Вихідні дані:

6

Пояснення: оптимальний відрізок — ~[4, -1, 2, 1]~ (елементи з 4-го по 7-й), його сума дорівнює ~4 + (-1) + 2 + 1 = 6~.

Приклад 2

Вхідні дані:

1
-5

Вихідні дані:

-5

Пояснення: відрізок обов'язково має бути непорожнім, тому доводиться взяти єдиний елемент.

Приклад 3

Вхідні дані:

5
1 2 3 4 5

Вихідні дані:

15

Пояснення: оптимально взяти весь масив цілком.