CF1935B.Informatics in MAC

In the Master's Assistance Center, Nyam-Nyam was given a homework assignment in informatics.

There is an array $a$ of length $n$, and you want to divide it into $k \gt 1$ subsegments$^{\dagger}$ in such a way that the $\operatorname{MEX} ^{\ddagger}$ on each subsegment is equal to the same integer.

Help Nyam-Nyam find any suitable division, or determine that it does not exist.

$^{\dagger}$A division of an array into $k$ subsegments is defined as $k$ pairs of integers $(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$ such that $l_i \le r_i$ and for each $1 \le j \le k - 1$, $l_{j + 1} = r_j + 1$, and also $l_1 = 1$ and $r_k = n$. These pairs represent the subsegments themselves.

$^{\ddagger}\operatorname{MEX}$ of an array is the smallest non-negative integer that does not belong to the array.

For example:

• $\operatorname{MEX}$ of the array $[2, 2, 1]$ is $0$, because $0$ does not belong to the array.
• $\operatorname{MEX}$ of the array $[3, 1, 0, 1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• $\operatorname{MEX}$ of the array $[0, 3, 1, 2]$ is $4$, because $0$, $1$, $2$, and $3$ belong to the array, but $4$ does not.

在硕士生辅导中心，Nyam-Nyam 收到了一道信息学作业题。

给定一个长度为 $n$ 的数组 $a$，你需要将其划分为 $k > 1$ 个子段$^{\dagger}$，使得每个子段的 $\operatorname{MEX}^{\ddagger}$ 均等于同一个整数。

请帮助 Nyam-Nyam 找出任意一种满足条件的划分方式，或判定这样的划分不存在。

$^{\dagger}$ 数组划分为 $k$ 个子段，定义为 $k$ 对整数 $(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$，满足：$l_i \le r_i$；对每个 $1 \le j \le k - 1$，有 $l_{j + 1} = r_j + 1$；且 $l_1 = 1$，$r_k = n$。这些数对即表示各子段本身。

$^{\ddagger}\operatorname{MEX}$（最小缺失非负整数）指不属于该数组的最小非负整数。

例如：

• 数组 $[2, 2, 1]$ 的 $\operatorname{MEX}$ 是 $0$，因为 $0$ 不在该数组中。
• 数组 $[3, 1, 0, 1]$ 的 $\operatorname{MEX}$ 是 $2$，因为 $0$ 和 $1$ 在该数组中，但 $2$ 不在。
• 数组 $[0, 3, 1, 2]$ 的 $\operatorname{MEX}$ 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 都在该数组中，但 $4$ 不在。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt n$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \lt n$），表示数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, output a single integer $-1$ if a suitable division does not exist.

Otherwise, on the first line, output an integer $k$ ($2 \le k \le n$) — the number of subsegments in the division.

Then output $k$ lines — the division into subsegments. The $i$-th line should contain two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the boundaries of the $i$-th subsegment.

The following conditions must be satisfied:

• For all $1 \le j \le k - 1$, $l_{j + 1} = r_j + 1$;
• $l_1 = 1$, $r_k = n$.

If there are multiple possible solutions, output any of them.

对于每个测试用例，若不存在满足条件的划分，则输出单个整数 $-1$。

否则，在第一行输出一个整数 $k$（$2 \le k \le n$）—— 划分所得子区间的数量。

随后输出 $k$ 行，表示该划分结果。第 $i$ 行应包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）—— 表示第 $i$ 个子区间的左右边界。

需满足以下条件：

• 对所有 $1 \le j \le k - 1$，有 $l_{j + 1} = r_j + 1$；
• $l_1 = 1$，$r_k = n$。

若存在多种可行解，输出任意一种即可。

In the first test case, the array $a$ can be divided into $2$ subsegments with boundaries $[1, 1]$ and $[2, 2]$:

• $\operatorname{MEX}$ of the first subsegment $[0]$ is $1$, as $0$ belongs to the subsegment, but $1$ does not.
• $\operatorname{MEX}$ of the second subsegment $[0]$ is $1$, as $0$ belongs to the subsegment, but $1$ does not.

In the second test case, it can be proven that the required division does not exist.

In the third test case, the array $a$ can be divided into $3$ subsegments with boundaries $[1, 3]$, $[4, 5]$, $[6, 8]$:

• $\operatorname{MEX}$ of the first subsegment $[0, 1, 7]$ is $2$, as $0$ and $1$ belong to the subsegment, but $2$ does not.
• $\operatorname{MEX}$ of the second subsegment $[1, 0]$ is $2$, as $0$ and $1$ belong to the subsegment, but $2$ does not.
• $\operatorname{MEX}$ of the third subsegment $[1, 0, 3]$ is $2$, as $0$ and $1$ belong to the subsegment, but $2$ does not.

在第一个测试用例中，数组 $a$ 可被划分为 $2$ 个子段，边界分别为 $[1, 1]$ 和 $[2, 2]$：

• 第一个子段 $[0]$ 的 $\operatorname{MEX}$ 为 $1$，因为 $0$ 属于该子段，但 $1$ 不属于。
• 第二个子段 $[0]$ 的 $\operatorname{MEX}$ 为 $1$，因为 $0$ 属于该子段，但 $1$ 不属于。

在第二个测试用例中，可以证明所要求的划分不存在。

在第三个测试用例中，数组 $a$ 可被划分为 $3$ 个子段，边界分别为 $[1, 3]$、$[4, 5]$ 和 $[6, 8]$：

• 第一个子段 $[0, 1, 7]$ 的 $\operatorname{MEX}$ 为 $2$，因为 $0$ 和 $1$ 属于该子段，但 $2$ 不属于。
• 第二个子段 $[1, 0]$ 的 $\operatorname{MEX}$ 为 $2$，因为 $0$ 和 $1$ 属于该子段，但 $2$ 不属于。
• 第三个子段 $[1, 0, 3]$ 的 $\operatorname{MEX}$ 为 $2$，因为 $0$ 和 $1$ 属于该子段，但 $2$ 不属于。