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

Есть $$$n$$$ детей, стоящих в очереди, и доброта $$$i$$$-го ребенка равна $$$a_i$$$. Санта решает, какие дети попадут в хороший список, а какие в плохой.

Переменная $$$X$$$ изначально равна $$$0$$$. Санта выполнит следующую операцию ровно $$$n-1$$$ раз:

  • Сначала выберите первого или второго ребенка в очереди и удалите его из очереди.
  • Пусть доброта выбранного ребёнка равняется $$$w$$$.
    • Если был выбран первый ребенок, запишите его в хороший список и прибавьте $$$w$$$ к $$$X$$$.
    • Если был выбран второй ребенок, запишите его в плохой список и вычтите $$$w$$$ из $$$X$$$.

Обратите внимание, что после всех операций останется ровно один ребенок, который не будет отнесён ни к одному списку.

Определите максимальное возможное значение $$$X$$$, которое Санта может получить после выполнения всех $$$n-1$$$ операций.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — количество детей.

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

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

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

Для каждого набора входных данных выведите одно целое число — максимальное возможное значение $$$X$$$, которое Санта может получить после выполнения всех $$$n-1$$$ операций.

Пример
Входные данные
7
2
2 -3
4
1 4 3 4
4
-4 2 3 -6
5
-2 -3 4 10 -9
5
-12345678 -1000000000 -999999999 1000000000 -999999999
2
-7 1
5
7 -6 -1 -8 -8
Выходные данные
3
8
4
15
2987654321
-1
29
Примечание

В первом наборе входных данных Санта выполнит ровно одну операцию. Если он выберет первого ребенка, он добавит $$$a_1=2$$$ к $$$X$$$, чтобы получить $$$X=2$$$; если он выберет второго ребенка, он вычтет $$$a_2=-3$$$ из $$$X$$$, чтобы получить $$$X=3$$$. Таким образом, ответ — $$$3$$$.

Во втором наборе входных данных оптимально выбрать первого ребенка во всех трех операциях. Значение $$$X$$$ будет $$$1+4+3=8$$$.

В третьем наборе входных данных ниже представлена оптимальная последовательность операций:

#Тип операцииДоброта оставшихся детей$$$X$$$ после операции
0 —$$$[-4, 2, 3, -6]$$$$$$0$$$
1Первый$$$[2, 3, -6]$$$$$$-4$$$
2Первый$$$[3, -6]$$$$$$-2$$$
3Второй$$$[3]$$$$$$4$$$

В четвертом наборе входных данных ниже представлена оптимальная последовательность операций:

#Тип операцииДоброта оставшихся детей$$$X$$$ после операции
0 —$$$[-2, -3, 4, 10, -9]$$$$$$0$$$
1Второй$$$[-2, 4, 10, -9]$$$$$$3$$$
2Первый$$$[4, 10, -9]$$$$$$1$$$
3Первый$$$[10, -9]$$$$$$5$$$
4Первый$$$[-9]$$$$$$15$$$