B. Префикс
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a_1, a_2, \ldots, a_n$$$.

Для каждого индекса $$$i = 2, 3, \ldots, n$$$ по порядку выполните следующие действия:

  • Положите $$$s = a_1 + a_2 + \ldots + a_{i-1}$$$.
  • Замените $$$a_i$$$ на одно из следующих трёх значений: $$$a_i - s$$$, $$$a_i$$$ или $$$a_i + s$$$.

Среди всех возможных вариантов выбора найдите максимальное значение $$$\max(a_1, a_2, \ldots, a_n)$$$ после описанного процесса.

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

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

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$2 \le n \le 50$$$).

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

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

Для каждого набора входных данных выведите одно целое число — максимально возможное значение $$$\max(a_1, a_2, \ldots, a_n)$$$.

Обратите внимание, что ответ для некоторых наборов входных данных не помещается в 32-битный целочисленный тип, поэтому в своём языке программирования следует использовать как минимум 64-битный целочисленный тип (например, long long в C++).

Пример
Входные данные
4
5
3 -5 1 -4 2
2
-1 2
3
1 2 3
3
-2 -2 -2
Выходные данные
24
3
7
4
Примечание

В первом наборе входных данных итоговый массив можно сделать равным $$$[3, -8, -4, -13, 24]$$$, поэтому ответ равен $$$24$$$.

Во втором наборе входных данных при $$$i = 2$$$ имеем $$$s = a_1 = -1$$$. Если заменить $$$a_2$$$ на $$$a_2 - s = 2 - (-1) = 3$$$, ответ будет равен $$$3$$$.

В третьем наборе входных данных итоговый массив можно сделать равным $$$[1, 3, 7]$$$, поэтому ответ равен $$$7$$$.

В четвёртом наборе входных данных замена $$$a_2$$$ на $$$a_2 + s = -4$$$ приводит к тому, что получаем $$$s = -6$$$ при $$$i = 3$$$. Если заменить $$$a_3$$$ на $$$a_3 - s = -2 - (-6) = 4$$$, итоговый массив будет равен $$$[-2, -4, 4]$$$, поэтому ответ равен $$$4$$$.