Гарний — Eolymp

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) — кількість елементів у масиві.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $- 1 0^{4} \leq a_{i} \leq 1 0^{4}$ -10^4 \leq a_i \leq 10^4) — елементи масиву.

Вихідні дані

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

Приклади

\begin{example}\exmp{5-2 1 -3 4 -1 2 1 -5 4}{6}\end{example}

Приклад 1

Loading

Приклад 2

Loading

Примітка

У наведеному прикладі підмасив з найбільшою сумою — це [4, -1, 2, 1], сума якого дорівнює $6$ .