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

Сегодня Лёше привезли массив чисел $$$a_1, a_2, \dots, a_n$$$ длины $$$n$$$. Он может выполнить сколько угодно (возможно, ноль) операций, чтобы изменить массив.

За $$$1$$$ операцию Лёша может выбрать любые $$$l$$$ и $$$r$$$ такие, что $$$1 \leq l \leq r \leq n$$$, и домножить все элементы массива от $$$l$$$-го до $$$r$$$-го включительно на $$$-1$$$. Иными словами, за $$$1$$$ операцию Лёша может заменить подмассив $$$[a_l, a_{l + 1}, \dots, a_r]$$$ на $$$[-a_l, -a_{l + 1}, \dots, -a_r]$$$.

Например, пусть $$$n = 5$$$, массив равен $$$[1, -2, 0, 3, -1]$$$, $$$l = 2$$$ и $$$r = 4$$$, тогда после выполнения операции массив будет равен $$$[1, 2, 0, -3, -1]$$$.

Лёша опаздывает в школу, поэтому вы должны помочь ему найти максимальную возможную сумму элементов массива, которую можно получить выполнением произвольного количества операций, а также минимальное число операций, которое придется для этого сделать.

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

В первой строке дано одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

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

В следующей строке даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — элементы массива.

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

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

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

Обратите внимание, что ответ может не помещаться в стандартный целочисленный тип данных, поэтому не забудьте использовать 64-битный тип данных.

Пример
Входные данные
5
6
-1 7 -4 -2 5 -8
8
-1 0 0 -2 1 0 -3 0
5
2 -1 0 -3 -7
5
0 -17 0 1 0
4
-1 0 -2 -1
Выходные данные
27 3
7 2
13 1
18 1
4 1
Примечание

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

В первом примере Лёша может применить операции: $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(6, 6)$$$.

Во втором примере для получения наибольшей суммы нужно выполнить операции: $$$(1, 8)$$$, $$$(5, 6)$$$.

В четвёртом примере необходимо нужно применить всего лишь одну операцию — $$$(2, 3)$$$.