You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

众所周知, 一个同学考试评级为 -, 是一件很丢人的事情, 所以老师会对分数为 - 的同学进行修改.

题目描述

我们班有 $n$ 个同学, 每个同学都有一个值 $a_i$ 考试评级, 老师可以对连续一段同学进行操作, 将 $a_i$ 变为 $-a_i$

比如我们有三名同学 $1, -5, -9$, 那我们可以通过修改一次操作使他们变为 $1, 5, 9$

现在老师想知道, 在最少修改多少次之后, 可以使得班级内每个人的评级之和最大.

数据格式

输入格式

第一行输入一个整数 $t$, 表示有 $t$ 组数据.

接下来是每组数据, 第一行为一个整数 $n$, 表示有 $n$ 名同学,

接下来一行是 $n$ 个整数 $a_i$, 表示第 $i$ 名同学的考试评级.

输出格式

输出 $t$ 行, 每行两个整数, 第一个整数表示最大评级之和, 第二个整数表示最少修改次数,

样例

3
5
1 -2 3 -4 5
4
1 -9 -3 6
4
-2 2 -2 -2

15 2
19 1
8 2

数据范围

$1 <= t <= 100$

$1 <= n <= 1000$

$1 <= a_i <= 1000$