CF1843B.Long Long

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.

今天，Alex 得到了一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$。他可以执行任意多次操作（包括零次）来修改数组中的元素。

在一次操作中，Alex 可以任选满足 $1 \leq l \leq r \leq n$ 的下标 $l$ 和 $r$，并将数组中从第 $l$ 个到第 $r$ 个（含端点）的所有元素乘以 $-1$。换言之，Alex 可以在一次操作中将子数组 $[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 上学快迟到了，因此你需要帮助他找出：通过任意次数的操作所能得到的数组元素和的最大值，以及为达到该最大值所必需执行的最少操作次数。

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

第一行包含一个整数 $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$。

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.

对于每个测试用例，输出两个以空格分隔的数字：数组中数字的最大可能和，以及达到该和所需的最少操作次数。

注意，答案可能超出标准整数类型的表示范围，因此请务必使用 64 位整数类型。

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

以下每个测试用例中，仅给出众多可能的最短操作序列之一。存在其他同样长度且能达成元素最大和的操作序列。

在第一个测试用例中，Alex 可执行如下操作：$(1, 4)$、$(2, 2)$、$(6, 6)$。

在第二个测试用例中，为获得最大和，需执行如下操作：$(1, 8)$、$(5, 6)$。

在第四个测试用例中，仅需执行一次操作：$(2, 3)$。