Дано масив із ~n~ цілих чисел.

Ваше завдання — знайти максимальну суму значень у безперервному непорожньому підмасиві.

Введення

Перший рядок містить ціле число ~n~: розмір масиву.

У другому рядку є ~n~ цілих чисел ~x_1,x_2,\dots,x_n~: значення масиву.

Вихід

Вивести одне ціле число: максимальну суму підмасиву.

обмеження

• ~1 \le n \le 2 \cdot 10^5~
• ~-10^9 \le x_i \le 10^9~

приклад введення:

8
-1 3 -2 5 3 -5 2 2

приклад виведення:

9