题目描述

序列 $a_1, a_2, \dots, a_n$ 长度为 $n$. 有多种操作（包括不操作）来改变序列中的元素。

操作 $1$ 选择 区间 $l$ 到 $r$ （$1 \leq l \leq r \leq n$）, 并将 $l$ 到 $r$ 中的所有元素乘以 $-1$。换言之， 在 操作$1$ 后子串 $[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$ and $r = 4$, 在进行若干操作后变为 $[1, 2, 0, -3, -1]$.

请求出若干次（也可能是0次）操作后序列所有元素的最大和以及得到此和进行操作的最少次数。

输入

第一行包含一个整数 $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 \times 10^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

样例解释

第一个样例，可以用操作1，操作以下区间 ：$(1, 4)$, $(2, 2)$, $(6, 6)$.

第二个样例，可以操作以下区间： $(1, 8)$, $(5, 6)$.

对于第四个样例，只能操作 $(2, 3)$.