CF2085B.Serval and Final MEX

给定一个由 $n \ge 4$ 个非负整数组成的数组 $a$。

你需要对 $a$ 执行以下操作，直到其长度变为 $1$：

• 选择两个下标 $l$ 和 $r$（$1 \le {\color{red}{ l < r }} \le |a|$），将子数组 $[a_l, a_{l+1}, \ldots, a_r]$ 替换为一个整数 $\operatorname{mex}([a_l, a_{l+1}, \ldots, a_r])$。其中 $\operatorname{mex}(b)$ 表示整数集合 $b$ 的最小未出现值（MEX）$^{\text{∗}}$。具体来说，令 $x = \operatorname{mex}([a_l, a_{l+1}, \ldots, a_r])$，数组 $a$ 将变为 $[a_1, a_2, \ldots, a_{l-1}, x, a_{r+1}, a_{r+2}, \ldots, a_{|a|}]$。注意此操作后 $a$ 的长度将减少 $(r - l)$。

Serval 希望最终 $a$ 中的唯一元素为 $0$。请帮助他完成这一目标！

更正式地说，你需要找到一个操作序列，使得按顺序执行这些操作后，数组 $a$ 的长度变为 $1$，且该元素为 $0$。

可以证明，在题目约束下至少存在一个有效的操作序列，且任何有效操作序列的长度不超过 $n$。

注意：你不需要最小化操作次数。

$^{\text{∗}}$整数集合 $b_1, b_2, \ldots, b_k$ 的最小未出现值（MEX）定义为不包含在该集合中的最小非负整数 $x$。

每个测试包含多个测试用例。第一行输入测试用例数 $t$（$1 \le t \le 1000$）。接下来描述每个测试用例。

每个测试用例的第一行包含一个整数 $n$（$4 \le n \le 5000$）——数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le n$）——数组 $a$ 的元素。

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

对于每个测试用例：

• 第一行输出一个整数 $k$（$0 \le k \le n$）——操作序列的长度。
• 随后输出 $k$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i < r_i \le |a|$）——第 $i$ 次操作中选择的下标，其中 $|a|$ 表示操作前数组的长度。

若存在多个答案，输出任意一种即可。

第一个测试案例中，由于 $\operatorname{mex}([1,2,3,4]) = 0$，经过一次操作后数组变为 $[0]$。

第二个测试案例中，数组 $a$ 的变化如下：

$$[ \underline{0,1},0,0,1] \to [ \underline{2,0},0,1] \to [ \underline{1,0},1] \to [ \underline{2,1}] \to [ 0].$$

第三个测试案例中，数组 $a$ 的变化如下：

$$[ 0,0,0,0,\underline{0,0}] \to [ 0,0,\underline{0,0},1] \to [ \underline{0,0},1,1] \to [ \underline{1,1,1}] \to [ 0].$$

翻译由 DeepSeek R1 完成