构造零总和

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个只含 $-1$、$0$ 和 $1$ 的数组 $a_1,a_2,\ldots,a_n$。请把整个数组划分成若干个连续区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k]$，其中 $l_1=1$、$r_k=n$，且相邻区间首尾相接。

区间 $[l,r]$ 的交错和定义为

要求所有区间交错和的总和等于 $0$。若存在多种合法划分，可以输出任意一种；不要求区间数最少。若不存在合法划分，需要报告无解。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

每个测试用例的第一行包含一个整数 $n$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例，若无解，输出一行 -1。

否则先输出区间数 $k$，随后输出 $k$ 行，每行两个整数 $l_i,r_i$。这些区间必须恰好、不重不漏地覆盖 $[1,n]$，并使全部区间交错和的总和为 $0$。

样例输入 1

5
4
0 0 0 0
7
-1 1 0 1 0 1 0
5
0 -1 1 0 1
3
1 0 1
1
1

样例输出 1

4
1 1
2 2
3 3
4 4
4
1 1
2 2
3 5
6 7
-1
2
1 1
2 3
-1

数据范围

对于所有数据，$1\le t\le 10\,000$，$1\le n\le 200\,000$，$a_i\in\{-1,0,1\}$，且所有测试用例的 $n$ 之和不超过 $200\,000$。