Есть ряд из \(n\) слизней. У каждого слизня есть некоторая целочисленная ценность, связанная с ним (ценность может быть также меньше нуля или равна нулю).
Любой из слизняков может съесть любого из своих соседей (ближайшего к нему слизня слева или справа, при условии что такой слизень есть).
Когда слизень с ценностью \(x\) съедает слизня со значением \(y\), то съеденный слизень исчезает, а ценность оставшегося слизня становится равной \(x - y\).
Слизни будут есть друг друга, пока не останется ровно один слизень.
Выясните какая наибольшая возможная ценность может оказаться у последнего слизня.
Выходные данные
Выведите одно число — наибольшую возможную ценность у последнего слизня.
Примечание
В первом примере одним из способов получить последнего слизня с ценностью \(4\) следующий:
- Второй слизень съедает третьего, ряд теперь содержит слизней \(2, -1, 1\)
- Второй слизень съедает третьего, ряд теперь содержит слизней \(2, -2\)
- Первый слизень съедает второго, ряд теперь содержит одного слизня \(4\)
Во втором примере первый слизень может есть слизней слева направо, тем самым получая итоговую ценность \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 1 2 1
|
4
|
|
2
|
5
0 -1 -1 -1 -1
|
4
|