D. Слизняки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть ряд из $$$n$$$ слизней. У каждого слизня есть некоторая целочисленная ценность, связанная с ним (ценность может быть также меньше нуля или равна нулю).

Любой из слизняков может съесть любого из своих соседей (ближайшего к нему слизня слева или справа, при условии что такой слизень есть).

Когда слизень с ценностью $$$x$$$ съедает слизня со значением $$$y$$$, то съеденный слизень исчезает, а ценность оставшегося слизня становится равной $$$x - y$$$.

Слизни будут есть друг друга, пока не останется ровно один слизень.

Выясните какая наибольшая возможная ценность может оказаться у последнего слизня.

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

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 500\,000$$$) — количество слизней в ряду.

Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$), где $$$a_i$$$ — это ценность $$$i$$$-го слизня.

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

Выведите одно число — наибольшую возможную ценность у последнего слизня.

Примеры
Входные данные
4
2 1 2 1
Выходные данные
4
Входные данные
5
0 -1 -1 -1 -1
Выходные данные
4
Примечание

В первом примере одним из способов получить последнего слизня с ценностью $$$4$$$ следующий:

  • Второй слизень съедает третьего, ряд теперь содержит слизней $$$2, -1, 1$$$
  • Второй слизень съедает третьего, ряд теперь содержит слизней $$$2, -2$$$
  • Первый слизень съедает второго, ряд теперь содержит одного слизня $$$4$$$

Во втором примере первый слизень может есть слизней слева направо, тем самым получая итоговую ценность $$$4$$$.