题目描述

你迷失在森林深处，陪伴你的只有你的白鼬。它的初始攻击力为 $1$，是你唯一的初始野兽。

一条小道从眼前伸向远方。小道上有 $n$ 个事件标志，每个标志属于以下事件之一：

• $\textbf{卡牌选择}$：一位森林的住民加入了你的队伍。你获得了一只额外的野兽，它的初始攻击力为 $1$。
• $\textbf{神秘石头}$：你被迫进行一次牺牲。你选择队伍中的两只野兽进行仪式：一只野兽将永远消失，而它的攻击力将加给另一只野兽。若你无法执行仪式，你将无法继续前进。
• $\textbf{分岔路}$：你可以决定进行一次卡牌选择或神秘石头。你不能决定什么都不做。

当你穿过崎岖的路面时，事件将依次触发。在所有事件完成后，你的野兽的平均攻击力最大能达到多少？

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 10^6$）表示事件的数量。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$-1 \le a_i \le 1$），其中 $a_i$ 表示第 $i$ 个事件标志的类型：$1$ 表示卡牌选择，$-1$ 表示神秘石头，$0$ 表示分岔路。

保证所有数据 $n$ 之和不超过 $10^6$。

输出格式

每组数据输出一行。

如果无法完成所有事件，输出整数 $-1$。

否则可以证明答案是一个有理数 $\frac{p'}{q'}$。输出两个整数 $p$ 和 $q$，其中 $\frac{p}{q}$ 是 $\frac{p'}{q'}$ 的最简分数表示。

称 $\frac{p}{q}$ 是 $\frac{p'}{q'}$ 的最简分数表示，若 $\frac{p}{q} = \frac{p'}{q'}$ 且 $p$ 和 $q$ 的最大公约数为 $1$。

6
7
1 1 1 -1 1 1 -1
4
1 0 -1 0
4
0 -1 -1 0
1
0
2
0 0
1
-1

3 2
3 1
-1
1 1
2 1
-1

提示

对第一组样例数据解释如下：

$$\begin{array}{|c|c|c|} \hline \textbf{事件} & \textbf{行动} & \textbf{野兽} \\ \hline 1 & 获得额外的野兽 & \{1, 1\} \\ \hline 1 & 获得额外的野兽 & \{1, 1, 1\} \\ \hline 1 & 获得额外的野兽 & \{1, 1, 1, 1\} \\ \hline -1 & 选择攻击力为\ 1 \ 和\ 1 \ 的野兽 & \{2, 1, 1\} \\ \hline 1 & 获得额外的野兽 & \{2, 1, 1, 1\} \\ \hline 1 & 获得额外的野兽 & \{2, 1, 1, 1, 1\} \\ \hline -1 & 选择攻击力为\ 2 \ 和\ 1 \ 的野兽 & \{3, 1, 1, 1\} \\ \hline \end{array} $$

对第二组样例数据解释如下：

$$\begin{array}{|c|c|c|} \hline \textbf{事件} & \textbf{行动} & \textbf{野兽} \\ \hline 1 & 获得额外的野兽 & \{1, 1\} \\ \hline 0 & 进行卡牌选择并获得额外的野兽 & \{1, 1, 1\} \\ \hline -1 & 选择攻击力为\ 1 \ 和\ 1 \ 的野兽 & \{2, 1\} \\ \hline 0 & 进行神秘石头并选择攻击力为\ 2 \ 和\ 1 \ 的野兽 & \{3\} \\ \hline \end{array} $$

平均攻击力为 $\frac{3}{1}$。

对第三组样例数据解释如下：

$$\begin{array}{|c|c|c|} \hline \textbf{事件} & \textbf{行动} & \textbf{野兽} \\ \hline 0 & 进行卡牌选择并获得额外的野兽 & \{1, 1\} \\ \hline -1 & 选择攻击力为\ 1 \ 和\ 1 \ 的野兽 & \{2\} \\ \hline -1 & 没有足够的野兽 & 失败 \\ \hline \end{array} $$