← 返回题目列表

Codeforces · 2085/B

B. Serval 和最终的 MEX

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

给定一个数组 $$$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|$$$ 表示执行此操作之前的数组。

如果有多个答案,您可以打印其中任何一个。

示例

输入
复制

6
4
1 2 3 4
5
0 1 0 0 1
6
0 0 0 0 0 0
6
5 4 3 2 1 0
4
0 0 1 1
4
1 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]。 $$$$$$