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.

题目描述

一个序列的中位数的定义为：将这个序列 从小到大 排序后，位于中间位置的数就是中位数，有以下两种情况：

• 当序列包含 奇数 个数字时候，中间的那个数字 即为中位数，例如 $[1,2,3,4,5]$ 的中位数是 $3$
• 当序列包含 偶数 个数字时候，中间两个数字的平均值（向下取整） 即为中位数，例如 $[1,2,3,4,5,6]$ 的中位数是 $(3+4)/2=3$

现在张老师给定了一个长度为 $n$ 的序列，分别为 $a_1,a_2,a_3 \dots a_n$

特别的，本题中 $a$ 序列的每个元素只会是 $0$ 或 $1$。

张老师希望将这个序列进行分割，分割成若干连续的区间（长度至少为 $1$）

而一种分割方案的价值为分割出所有区间的中位数之和

张老师想知道在所有不同的方案中，最小价值和最大价值分别是多少？

输入格式

本题包含多组测试数据

输入第一行包含一个整数 $T$ 表示有 $T$ 组测试数据

对于每组测试数据：

第一行一个整数 $n$ 表示序列长度

第二行包含 $n$ 个整数，$a_1,a_2,a_3 \dots a_n$

输出格式

对于每组测试数据，输出一行包含两个整数，分别表示最小价值和最大价值，中间用空格隔开

样例 1

2
3
0 1 1
4
0 1 0 1

1 2
0 2

样例解释

对于第一组数据共有 $4$ 种划分方法：

1. [0], [1], [1]，此时的中位数分别为：$0, 1, 1$，数组的价值为 $0 + 1 + 1 = 2$
2. [0, 1], [1]，此时的中位数分别为：$(0+1)/2=0, 1$，数组的价值为 $0 + 1 = 1$；
3. [0], [1, 1]，此时的中位数分别为：$0, (1+1)/2=1$，数组的价值为 $0 + 1 = 1$；
4. [0, 1, 1]，此时的中位数是 $1$，数组的价值为 $1$。

其中最小价值为 $1$，最大价值为 $2$

数据范围

特别的，对于所有数据满足: $a$ 序列仅包含 $0$ 和 $1$