eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Прибыль

Прибыль

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Коровы открыли новый бизнес, и Фермер Джон хочет видеть, насколько они хорошо его ведут. Бизнес работает n~(1 \le n ≤ 10^5) дней, и в каждый i-ый день коровы записывают свою чистую прибыль P_i~(-1000 \le P_i \le 1000).

Фермер Джон хочет найти самую большую прибыль, которую получили коровы в течение любого последовательного периода времени (обратите внимание, что последовательный период времени может иметь длину от одного дня до n дней). Помогите ему, написав программу для нахождения величины наибольшей непрерывной прибыли.

Входные данные

Первая строка содержит целое число n. Каждая из следующих n строк содержит одно целое число P_i.

Выходные данные

Выведите значение максимальной суммы прибыли за любой последовательный период времени.

Пример

Входные данные #1
7
-3
4
9
-2
-5
8
-3
Выходные данные #1
14