E. Отрицательные и положительные
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ состоящий из $$$n$$$ элементов, найдите максимально возможную сумму, которая может быть у массива после выполнения следующей операции любое количество раз:

  • Выбрать $$$2$$$ соседних элемента и поменять их знаки. Иными словами, выбрать индекс $$$i$$$ такой, что $$$1 \leq i \leq n - 1$$$ и присвоить $$$a_i = -a_i$$$ и $$$a_{i+1} = -a_{i+1}$$$.
Входные данные

Каждый тест состоит из множества наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов. Затем следуют описания наборов.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — длину массива.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$), разделенных пробелами.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

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

Для каждого набора входных данных выведите максимально возможную сумму, которая может получится у массива, если мы применим описанную выше операцию любое количество раз.

Пример
Входные данные
5
3
-1 -1 -1
5
1 5 -5 0 2
3
1 2 3
6
-1 10 9 8 7 6
2
-1 -1
Выходные данные
1
13
6
39
2
Примечание

В первом наборе, выполнив операцию над первыми двумя элементами, мы можем изменить массив с $$$[-1, -1, -1]$$$ на $$$[1, 1, -1]$$$. Можно доказать, что этот массив дает максимально возможную сумму, которая равна $$$1 + 1 + (-1) = 1$$$.

Во втором наборе, выполнив операцию над $$$-5$$$ и $$$0$$$, мы изменим массив с $$$[1, 5, -5, 0, 2]$$$ на $$$[1, 5, -(-5), -0, 2] = [1, 5, 5, 0, 2]$$$, который имеет максимальную сумму, так как все элементы неотрицательны. Так, ответ: $$$1 + 5 + 5 + 0 + 2 = 13$$$.

В третьем наборе массив уже содержит только положительные числа, поэтому выполнять операции не нужно. Ответ — это просто сумма всего массива, которая равна $$$1 + 2 + 3 = 6$$$.