← 返回题目列表

Codeforces · 1935/B

B. MAC 中的信息学

中文机器翻译题面 查看原题

在硕士援助中心,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$$$ 行 — 划分为子段。第 $$$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$$$。

如果有多种可能的解决方案,则输出其中任何一个。

示例

输入 #1

5
2
0 0
5
0 1 2 3 4
8
0 1 7 1 0 1 0 3
3
2 2 2
4
0 1 2 0

输出 #1

2
1 1
2 2
-1
3
1 3
4 5
6 8
3
1 1
2 2
3 3
-1

注意

在第一个测试用例中,数组 $$$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$$$ 不属于该子段。