Long Long

题面翻译

题目描述

给出一个包含 $n$ 个数字的数列 $a$。你可以执行任意次操作，每次操作可以更改 [l, r] 范围内的正负性（正数变负，负数变正，0 不变）。你要使得数列每个元素之和尽量大，问最小的操作次数。

多组询问。

输入格式

第一行一个整数 $T$，表示询问组数。

每一组数据第一行输入一个整数 $n$，表述数列长度。

第二行 $n$ 个整数 $a_1,a_2,...,a_n​$ 表示数列 $a$ 中的每个元素。

输出格式

对于每组数据，每一行，输出两个用空格隔开的整数，分别表示最大可能的数列元素之和与最小操作次数。

数据范围

$1\leq T \leq 10^4$

$1\leq n \leq 2\times10^5$

$-10^9\leq a_i \leq 10^9$

数据保证所有询问的 $n$ 总和不超过 $2\times10^5$。

提示

统计数字之和部分可能会爆 int，请选择合适的储存方式。

题目描述

Today Alex was brought array $a_1, a_2, \dots, a_n$ of length $n$ . He can apply as many operations as he wants (including zero operations) to change the array elements.

In $1$ operation Alex can choose any $l$ and $r$ such that $1 \leq l \leq r \leq n$ , and multiply all elements of the array from $l$ to $r$ inclusive by $-1$ . In other words, Alex can replace the subarray $[a_l, a_{l + 1}, \dots, a_r]$ by $[-a_l, -a_{l + 1}, \dots, -a_r]$ in $1$ operation.

For example, let $n = 5$ , the array is $[1, -2, 0, 3, -1]$ , $l = 2$ and $r = 4$ , then after the operation the array will be $[1, 2, 0, -3, -1]$ .

Alex is late for school, so you should help him find the maximum possible sum of numbers in the array, which can be obtained by making any number of operations, as well as the minimum number of operations that must be done for this.

输入格式

The first line contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains one integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) — length of the array.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $-10^9 \leq a_i \leq 10^9$ ) — elements of the array.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$ .

输出格式

For each test case output two space-separated numbers: the maximum possible sum of numbers in the array and the minimum number of operations to get this sum.

Pay attention that an answer may not fit in a standard integer type, so do not forget to use 64-bit integer type.

样例 #1

样例输入 #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

提示

Below, for each test case, only one of the possible shortest sequences of operations is provided among many. There are others that have the same length and lead to the maximum sum of elements.

In the first test case, Alex can make operations: $(1, 4)$ , $(2, 2)$ , $(6, 6)$ .

In the second test case, to get the largest sum you need to make operations: $(1, 8)$ , $(5, 6)$ .

In the fourth test case, it is necessary to make only one operation: $(2, 3)$ .