Коровы открыли новый бизнес, и Farmer John хочет узнать, насколько хорошо у них идут дела. Бизнес работает уже $N$ ($1 \leq N \leq 100{,}000$) дней, и каждый день $i$ коровы записывали чистую прибыль $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$).

Farmer John хочет найти наибольшую общую прибыль, которую коровы получили за какой-либо непрерывный период. (Учтите, что длина такого периода может составлять от одного дня до $N$ дней.) Помогите ему, написав программу для вычисления наибольшей суммы последовательных прибылей.

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

Читайте данные из стандартного ввода.

• Строка 1: одно целое число $N$.
• Строки $2..N+1$: строка $i+1$ содержит одно целое число $P_i$.

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

Записывайте результат в стандартный вывод.

• Строка 1: одно целое число — максимальная сумма прибыли за какой-либо непрерывный период.

Примеры

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

7
-3
4
9
-2
-5
8
-3

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

14

Примечание

Максимальная сумма получается при сложении чисел со второго по шестое (4, 9, -2, -5, 8) и равна 14.

Автор задачи: Neal Wu, 2007