← 返回题目列表

Codeforces · 1843/B

B. 长长

中文机器翻译题面 查看原题

今天 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)$$$。