Есть ряд из \(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\) следующий:
Во втором примере первый слизень может есть слизней слева направо, тем самым получая итоговую ценность \(4\).
4 2 1 2 1
4
5 0 -1 -1 -1 -1
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач