D. Маша и Глеб переезжают
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маша и Глеб решили переехать в город M и задумались о приобретении там земли. Всего в продаже имеются $$$n$$$ земельных участков, расположенных последовательно вдоль дороги. Для каждого участка известна его цена. Некоторые цены даже могут быть отрицательными — в таких случаях город сам готов заплатить покупателю, лишь бы скинуть с себя обязанности по содержанию проблемных участков.

Маша хочет выбрать себе один или несколько участков, идущих обязательно подряд, чтобы их можно было слить в один. Аналогично хочет поступить и Глеб. Кроме того, Маша и Глеб хотят стать соседями — то есть, после выполнения слияний их объединённые участки должны оказаться соседними.

Глеб очень ленив, поэтому он попросил Машу заняться подбором участков для них обоих. А Маша уже устала от лени Глеба, поэтому она решила его проучить и выбрать участки так, чтобы разница суммарных стоимостей участков Глеба и участков Маши оказалась как можно больше. Напишите программу для нахождения этой максимальной разности.

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

В первой строке входных данных записано число $$$n$$$ $$$(2 \le n \le 10^5)$$$. В следующих $$$n$$$ строках записаны числа $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ — цены участков ($$$-10^9 \le a_i \le 10^9)$$$.

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

Выведите одно целое число — максимально возможную разницу суммарных стоимостей участков Глеба и Маши.

Система оценки

Решения, правильно работающие при $$$n \le 10$$$, будут набирать не менее 15 баллов. Решения, правильно работающие при $$$n \le 200$$$, будут набирать не менее 30 баллов. Решения, правильно работающие при $$$n \le 3000$$$, будут набирать не менее 60 баллов.

Примеры
Входные данные
3
1
2
3
Выходные данные
4
Входные данные
7
1
2
-3
6
10
5
-100
Выходные данные
121
Примечание

Обратите внимание, что ответ может превышать возможное значение 32-битной целочисленной переменной. Поэтому необходимо использовать 64-битный целочисленный тип данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). В языке Python ничего дополнительно делать не требуется.

Выбор компилятора. Если вы сдаёте решение этой задачи на языке Python, не забудьте про возможность выбора компилятора pypy — возможно, с использованием его программа будет работать существенно быстрее.