Инвестор анализирует изменения капитала по дням. Для каждого из n дней известно целое число a_i — прирост капитала за этот день. Значение может быть как положительным, так и отрицательным.

Необходимо выбрать некоторый непустой непрерывный промежуток дней так, чтобы суммарный прирост капитала на нём был максимальным.

Рассмотрим префиксные суммы. Тогда суммарный прирост на отрезке дней [l+1, r] равен pre[r] - pre[l], где pre[k] — сумма первых k значений. Значит, для каждого r оптимальный промежуток, заканчивающийся в дне r, получается как pre[r] минус минимальная префиксная сумма среди всех предыдущих позиций.

Требуется найти максимальный суммарный прирост капитала на непустом промежутке дней.

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

В первой строке задано число n (1 <= n <= 2*10^5).

Во второй строке заданы n целых чисел a_i (-10^9 <= a_i <= 10^9) — прирост капитала по дням.

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

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

Ответ может не помещаться в 32-битный тип.

Ограничения

• 1 <= n <= 2*10^5
• -10^9 <= a_i <= 10^9

Примеры

Пример 1

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

1
5

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

5

Пример 2

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

1
-7

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

-7