310500: CF1843B. Long Long

B. Long Longtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

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

Output

27 3
7 2
13 1
18 1
4 1

Note

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)$.

题目大意：
这个题目是关于一个数组操作的问题。给定一个长度为 n 的数组 a_1, a_2, ..., a_n，可以进行任意次数的操作（包括零次）来改变数组元素的值。每次操作可以选择任意的 l 和 r（1 ≤ l ≤ r ≤ n），并将数组中从 l 到 r（包括 l 和 r）的所有元素乘以 -1。换句话说，就是将子数组 [a_l, a_{l+1}, ..., a_r] 替换为 [-a_l, -a_{l+1}, ..., -a_r]。目标是找到通过进行任意次数的操作可以得到的最大的数组元素和，以及得到这个和所需的最小操作次数。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数 n（1 ≤ n ≤ 2 × 10^5），表示数组的长度。
- 第二行包含 n 个整数 a_1, a_2, ..., a_n（-10^9 ≤ a_i ≤ 10^9），表示数组的元素。
- 保证所有测试用例的 n 之和不超过 2 × 10^5。

输出：
- 对于每个测试用例，输出两个空格分隔的数字：可以得到的最大数组元素和以及得到这个和所需的最小操作次数。

注意：答案可能不适合标准的整数类型，因此不要忘记使用 64 位整数类型。

示例：
```
输入：
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
```

注意：对于每个测试用例，下面只提供了一个可能的最短操作序列之一。还有其他具有相同长度并导致元素和最大的操作序列。题目大意： 这个题目是关于一个数组操作的问题。给定一个长度为 n 的数组 a_1, a_2, ..., a_n，可以进行任意次数的操作（包括零次）来改变数组元素的值。每次操作可以选择任意的 l 和 r（1 ≤ l ≤ r ≤ n），并将数组中从 l 到 r（包括 l 和 r）的所有元素乘以 -1。换句话说，就是将子数组 [a_l, a_{l+1}, ..., a_r] 替换为 [-a_l, -a_{l+1}, ..., -a_r]。目标是找到通过进行任意次数的操作可以得到的最大的数组元素和，以及得到这个和所需的最小操作次数。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数 n（1 ≤ n ≤ 2 × 10^5），表示数组的长度。 - 第二行包含 n 个整数 a_1, a_2, ..., a_n（-10^9 ≤ a_i ≤ 10^9），表示数组的元素。 - 保证所有测试用例的 n 之和不超过 2 × 10^5。 输出： - 对于每个测试用例，输出两个空格分隔的数字：可以得到的最大数组元素和以及得到这个和所需的最小操作次数。 注意：答案可能不适合标准的整数类型，因此不要忘记使用 64 位整数类型。 示例： ``` 输入： 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 ``` 注意：对于每个测试用例，下面只提供了一个可能的最短操作序列之一。还有其他具有相同长度并导致元素和最大的操作序列。