C. Прекрасная рандомизированная сумма
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Учиться, учиться и еще раз учиться — вот чем приходится заниматься Валере каждый будний день. Он учится в математической школе, где конечно же профильным предметом является математика. Учительница математики Валерия Валерьевна очень любит свой предмет и всячески пытается привить эту любовь ученикам. Однако её методы весьма сомнительны, так как ради достижения своей цели она постоянно дает детям очень объемные и сложные домашние задания. Несмотря на то что Валера вовсе не худший ученик в классе, с очередным домашним заданием, которое как всегда оказалось непростым, он не справился. Вот поэтому он и обратился к Вам за помощью. А задание у Валеры такое: пусть задана последовательность из n чисел. Назовем префиксом последовательности некоторое количество первых ее элементов (возможно нулевое), а суффиксом — некоторое количество последних ее элементов (возможно нулевое). Разрешается последовательно выполнить две операции - взять произвольный префикс последовательности и умножить все числа в нем на  - 1, а затем проделать такую же операцию с суффиксом (префикс и суффикс могут пересекаться). Какую наибольшую сумму элементов последовательности можно получить в результате этих двух действий?

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

В первой строке входного файла задано число n (1 ≤ n ≤ 105) — количество элементов в последовательности. Во второй строке n целых чисел ai ( - 104 ≤ ai ≤ 104) — сама последовательность.

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

В первой и единственной строке выходного файла выведете ответ на поставленную задачу.

Примеры
Входные данные
3
-1 -2 -3
Выходные данные
6
Входные данные
5
-4 2 0 5 0
Выходные данные
11
Входные данные
5
-1 10 -5 10 -2
Выходные данные
18