题目描述

给出一个包含 $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，请选择合适的储存方式。

样例

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