给定一个数组 $$$a$$$,由 $$$n\ge 4$$$ 个非负整数组成。
需要对$$$a$$$执行以下操作,直到其长度变为$$$1$$$:
- 选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$1\le {\color{red}{ l \lt 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$$$,而$$$a$$$ 中的最终元素为$$$0$$$。
可以证明,在问题的约束下,至少存在一个有效的操作序列,且任一有效操作序列的长度不超过$$$n$$$。
请注意,您这样做 不 需要尽量减少操作次数。
$$$^{\text{*}}$$$整数集合 $$$b_1, b_2, \ldots, b_k$$$ 的最小排除 (MEX) 被定义为集合 $$$b$$$ 中不出现的最小非负整数 $$$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 \lt r_i\le |a|$$$) — 您在第 $$$i$$$ 操作中选择的两个索引,其中 $$$|a|$$$ 表示执行此操作之前的数组。
如果有多个答案,您可以打印其中任何一个。
示例
输入复制
641 2 3 450 1 0 0 160 0 0 0 0 065 4 3 2 1 040 0 1 141 0 0 0
输出复制
1 1 4 4 1 2 1 2 1 2 1 2 4 5 6 3 4 1 2 1 3 3 4 5 4 5 1 4 2 1 2 1 3 2 2 4 1 2
注意
在第一个测试用例中,由于 $$$\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]。 $$$$$$