今天 Alex 被带来了长度为 $$$n$$$ 的数组 $$$a_1, a_2, \dots, a_n$$$。他可以应用任意数量的操作(包括零操作)来更改数组元素。
在 $$$1$$$ 操作中,Alex 可以选择任何 $$$l$$$ 和 $$$r$$$,使得 $$$1 \leq l \leq r \leq n$$$,并将数组中从 $$$l$$$ 到 $$$r$$$ 的所有元素乘以 $$$-1$$$。换句话说,Alex 可以在 $$$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]$$$。
Alex 上学迟到了,所以你应该帮助他找到数组中可能的最大数字之和(可以通过任意次数的运算获得),以及为此必须完成的最小运算次数。
输入
第一行包含一个整数 $$$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 位整数类型。
示例
输入 #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
输出 #1
27 3 7 2 13 1 18 1 4 1
注意
下面,对于每个测试用例,仅提供众多可能的最短操作序列中的一个。还有其他一些具有相同的长度并导致元素之和最大。
在第一个测试用例中,Alex 可以进行以下操作:$$$(1, 4)$$$、$$$(2, 2)$$$、$$$(6, 6)$$$。
在第二个测试用例中,要获得最大的总和,您需要进行以下操作:$$$(1, 8)$$$, $$$(5, 6)$$$。
在第四个测试用例中,只需要进行一个操作:$$$(2, 3)$$$。