Вам дан массив из \(n\) целых чисел \(a_1, a_2, \ldots, a_n\). Каждое число равно либо \(1\), либо \(-1\). Вы должны выполнить следующую операцию над массивом \(a\) ровно один раз:
Какое максимально возможное значение \(a_1 + a_2 + \ldots + a_n\) можно получить после применения вышеописанной операции?
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \le t \le 500\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого теста содержит одно целое число \(n\) (\(2 \le n \le 10^5\)) — длину массива \(a\).
Следующая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(a_i = 1\) либо \(a_i = -1\)).
Гарантируется, что сумма значений \(n\) по всем наборам входных данных не превосходит \(10^5\).
Для каждого набора входных данных в отдельной строке выведите максимально возможную сумму массива \(a\), которую вы можете получить в результате применения одной операции.
В первом случае мы можем выбрать индекс \(4\) и перевернуть знаки \(a_4\) и \(a_5\). После этой операции сумма будет равна \(-1+1+1+1+1 = 3\). Можно показать, что мы не можем сделать сумму больше этого значения.
В третьем наборе единственным вариантом является выбор индекса \(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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач