CF1935B Informatics in MAC

在 Master's Assistance Center，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$ 不在。

每组测试数据包含多组测试用例。第一行包含一个整数 $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 < n$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，如果不存在满足条件的划分，输出一行 $-1$。 否则，第一行输出一个整数 $k$（$2 \le k \le n$），表示划分的子段数量。 接下来输出 $k$ 行，每行两个整数 $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$。 如果存在多种方案，输出任意一种即可。

在第一个测试用例中，数组 $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$ 不在。 由 ChatGPT 4.1 翻译