A. Сумма-перевёртыш
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив из $$$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$$$ можно получить после применения вышеописанной операции?

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1
Выходные данные
3
3
-2
4
Примечание

В первом случае мы можем выбрать индекс $$$4$$$ и перевернуть знаки $$$a_4$$$ и $$$a_5$$$. После этой операции сумма будет равна $$$-1+1+1+1+1 = 3$$$. Можно показать, что мы не можем сделать сумму больше этого значения.

В третьем наборе единственным вариантом является выбор индекса $$$1$$$.