Вам дан массив из \(n\) целых чисел \(a_1, a_2, \ldots, a_n\). Каждое число равно либо \(1\), либо \(-1\). Вы должны выполнить следующую операцию над массивом \(a\) ровно один раз:
- Выбрать индекс \(i\) (\(1 \leq i < n\)) и перевернуть знаки \(a_i\) и \(a_{i+1}\). Здесь переворачивание знака означает, что \(-1\) будет заменено на \(1\), а \(1\) станет \(-1\).
Какое максимально возможное значение \(a_1 + a_2 + \ldots + a_n\) можно получить после применения вышеописанной операции?
Выходные данные
Для каждого набора входных данных в отдельной строке выведите максимально возможную сумму массива \(a\), которую вы можете получить в результате применения одной операции.
Примечание
В первом случае мы можем выбрать индекс \(4\) и перевернуть знаки \(a_4\) и \(a_5\). После этой операции сумма будет равна \(-1+1+1+1+1 = 3\). Можно показать, что мы не можем сделать сумму больше этого значения.
В третьем наборе единственным вариантом является выбор индекса \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1
|
3
3
-2
4
|