B. Long Long

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Today Alex was brought array a1,a2,…,an�1,�2,…,�� of length n�. He can apply as many operations as he wants (including zero operations) to change the array elements.

In 11 operation Alex can choose any l� and r� such that 1≤l≤r≤n1≤�≤�≤�, and multiply all elements of the array from l� to r� inclusive by −1−1. In other words, Alex can replace the subarray [al,al+1,…,ar][��,��+1,…,��] by [−al,−al+1,…,−ar][−��,−��+1,…,−��] in 11 operation.

For example, let n=5�=5, the array is [1,−2,0,3,−1][1,−2,0,3,−1], l=2�=2 and r=4�=4, then after the operation the array will be [1,2,0,−3,−1][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≤t≤1041≤�≤104) — number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains one integer n� (1≤n≤2⋅1051≤�≤2⋅105) — length of the array.

The second line contains n� integers a1,a2,…,an�1,�2,…,�� (−109≤ai≤109−109≤��≤109) — elements of the array.

It is guaranteed that the sum of n� for all test cases does not exceed 2⋅1052⋅105.

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.

Example

input

Copy

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

Copy

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)(1,4), (2,2)(2,2), (6,6)(6,6).

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

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

解题说明：此题是一道数学题，采用贪心算法，最大值肯定是所有数取绝对值相加，至于需要转换的次数，直接遍历查找其中的负数，如果负数单独出现就只转换一个负数，否则转换连续出现的负数。

#include <stdio.h>
#include <stdlib.h>
typedef long long LL;
int a[200010];int main()
{int t = 0;scanf("%d", &t);while (t--){int n = 0;scanf("%d", &n);LL cnt = 0, sum = 0;for (int i = 0; i < n; i++){scanf("%d", &a[i]);if (a[i] > 0){sum += a[i];}else{sum -= a[i];}}for (int i = 0, j = 0; i < n; i++){if (a[i] >= 0){continue;}j = i;while (a[j] <= 0){j++;}if (j != i){cnt++;}i = j - 1;}printf("%lld %lld\n", sum, cnt);}return 0;
}