A. Переставь и измени знак
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел. Вы должны выполнить следующие две операции с массивом (сначала первую, затем вторую):

  1. Произвольно переставить элементы массива или оставить порядок его элементов без изменений.
  2. Выбрать не более одного отрезка подряд идущих элементов и заменить знаки всех элементов на этом отрезке на противоположные. Формально, вы можете выбрать пару индексов $$$l, r$$$ такие, что $$$1 \le l \le r \le n$$$ и присвоить $$$a_i = -a_i$$$ для всех $$$l \le i \le r$$$. Заметим, что вы можете не выбирать пару индексов и оставить все знаки элементов без изменений.

Какова максимальная сумма элементов массива после последовательного выполнения двух операций (сначала первой, затем второй)?

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$) — количество элементов в массиве $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \le a_i \le 100$$$) — элементы массива.

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

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

Пример
Входные данные
8
3
-2 3 -3
1
0
2
0 1
1
-99
4
10 -2 -3 7
5
-1 -2 -3 -4 -5
6
-41 22 -69 73 -15 -50
12
1 2 3 4 5 6 7 8 9 10 11 12
Выходные данные
8
0
1
99
22
15
270
78
Примечание

В первом наборе входных данных вы можете сначала переставить массив, чтобы получился $$$[3,-2,-3]$$$ (операция 1), затем выбрать $$$l = 2, r = 3$$$ и получить сумму $$$3 + -((-2) + (-3)) = 8$$$ (операция 2).

Во втором наборе входных данных вы можете ничего не делать при выполнении обеих операций и получить сумму $$$0$$$.

В третьем наборе входных данных вы можете ничего не делать при выполнении обеих операций и получить сумму $$$0 + 1 = 1$$$.

В четвертом наборе входных данных вы можете сначала оставить порядок неизменным (операция 1), затем выбрать $$$l = 1, r = 1$$$ и получить сумму $$$-(-99) = 99$$$ (операция 2).

В пятом наборе входных данных вы можете сначала оставить порядок неизменным (операция 1), затем выбрать $$$l = 2, r = 3$$$ и получить сумму $$$10 + -((-2) + (-3)) + 7 = 22$$$ (операция 2).

В шестом наборе входных данных вы можете сначала оставить порядок неизменным (операция 1), затем выбрать $$$l = 1, r = 5$$$ и получить сумму $$$-((-1)+(-2)+(-3)+(-4)+(-5))=15$$$ (операция 2).