Условие:
Сегодня Лёше привезли массив чисел a1,a2,…,an длины n. Он может выполнить сколько угодно (возможно, ноль) операций, чтобы изменить массив.
За 1 операцию Лёша может выбрать любые l и r такие, что 1≤l≤r≤n, и домножить все элементы массива от l-го до r-го включительно на −1. Иными словами, за 1 операцию Лёша может заменить подмассив [al,al+1,…,ar] на [−al,−al+1,…,ar].
Например, пусть n=5, массив равен [1,−2,0,3,−1], l=2 и r=4, тогда после выполнения операции массив будет равен [1,2,0,−3,−1].
Лёша опаздывает в школу, поэтому вы должны помочь ему найти максимальную возможную сумму элементов массива, которую можно получить выполнением произвольного количества операций, а также минимальное число операций, которое придется для этого сделать.
Входные данные
В первой строке дано одно целое число t (1≤t≤104) — количество наборов входных данных.
В первой строке каждого набора входных данных дано одно целое число n (1≤n≤2⋅105) — длина массива.
В следующей строке даны n целых чисел a1,a2,…,an (−109≤ai≤109) — элементы массива.
Гарантируется, что сумма n по всем наборам входных данных не превышает 2⋅105.
Выходные данные
Для каждого набора входных данных выведите сначала максимальную возможную сумму массива, а затем через пробел минимальное количество операций, которое необходимо выполнить, чтобы получить такую сумму.
Обратите внимание, что ответ может не помещаться в стандартный целочисленный тип данных, поэтому не забудьте использовать 64-битный тип данных.
