Сегодня Лёше привезли массив чисел \(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]\).
Лёша опаздывает в школу, поэтому вы должны помочь ему найти максимальную возможную сумму элементов массива, которую можно получить выполнением произвольного количества операций, а также минимальное число операций, которое придется для этого сделать.
Выходные данные
Для каждого набора входных данных выведите сначала максимальную возможную сумму массива, а затем через пробел минимальное количество операций, которое необходимо выполнить, чтобы получить такую сумму.
Обратите внимание, что ответ может не помещаться в стандартный целочисленный тип данных, поэтому не забудьте использовать 64-битный тип данных.
Примечание
Далее для каждого тестового случая приводится только одна из возможных кратчайших последовательностей операций. Существуют и другие, которые имеют такую же длину и приводят к максимальной сумме элементов.
В первом примере Лёша может применить операции: \((1, 4)\), \((2, 2)\), \((6, 6)\).
Во втором примере для получения наибольшей суммы нужно выполнить операции: \((1, 8)\), \((5, 6)\).
В четвёртом примере необходимо нужно применить всего лишь одну операцию — \((2, 3)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|