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

Требуется найти такой непустой отрезок подряд идущих дней, чтобы суммарная прибыль за этот период была максимальной.

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

В первой строке задано число 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
-7

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

-7

Пример 2

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

5
1 -2 3 4 -1

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

7