给你一个 $$$n$$$ 整数数组,介于 $$$0$$$ 和 $$$n$$$ 之间(含)。
在一次操作中,您可以选择数组的任意元素并将其替换为数组元素的 MEX(操作后可能会发生变化)。
例如,如果当前数组为 $$$[0, 2, 2, 1, 4]$$$,则可以选择第二个元素并将其替换为当前元素的 MEX — $$$3$$$。数组将变为 $$$[0, 3, 2, 1, 4]$$$。
您必须使用最多 $$$2n$$$ 操作使数组非递减。
可以证明它总是可能的。请注意,您不必最小化操作次数。如果有很多解决方案,您可以打印其中任何一个。
–
数组 $$$b[1 \ldots n]$$$ 是非递减的当且仅当 $$$b_1 \le b_2 \le \ldots \le b_n$$$。
数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如:
- $$$[2, 2, 1]$$$ 的 MEX 是 $$$0$$$,因为 $$$0$$$ 不属于该数组。
- $$$[3, 1, 0, 1]$$$ 的 MEX 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于数组,但 $$$2$$$ 不属于该数组。
- $$$[0, 3, 1, 2]$$$ 的 MEX 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于该数组,但 $$$4$$$ 不属于该数组。
值得一提的是,长度为 $$$n$$$ 的数组的 MEX 始终在 $$$0$$$ 和 $$$n$$$ 之间(包含 $$$0$$$ 和 $$$n$$$)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1000$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — 数组的元素。请注意,它们不必是不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,您必须输出两行:
第一行必须包含一个整数 $$$k$$$ ($$$0 \le k \le 2n$$$) — 您执行的操作数。
第二行必须包含 $$$k$$$ 整数 $$$x_1, \ldots, x_k$$$ ($$$1 \le x_i \le n$$$),其中 $$$x_i$$$ 是为第 $$$i$$$ 操作选择的索引。
如果有很多解决方案,您可以找到其中任何一个。请记住,不需要最小化$$$k$$$。
示例
输入 #1
5 3 2 2 3 3 2 1 0 7 0 7 3 1 3 7 7 9 2 0 1 1 2 4 4 2 0 9 8 4 7 6 1 2 3 0 5
输出 #1
0 2 3 1 4 2 5 5 4 11 3 8 9 7 8 5 9 6 4 1 2 10 1 8 1 9 5 2 4 6 3 7
注意
在第一个测试用例中,数组已经是非递减的 ($$$2 \le 2 \le 3$$$)。
第二个测试用例的说明(每个操作修改的元素用红色表示):
- $$$a = [2, 1, 0]$$$ ;初始 MEX 为 $$$3$$$。
- $$$a = [2, 1, \color{红色}{3}]$$$ ;新的 MEX 为 $$$0$$$。
- $$$a = [\color{红色}{0}, 1, 3]$$$ ;新的 MEX 为 $$$2$$$。
- 最终数组是非递减的:$$$0 \le 1 \le 3$$$。
第三个测试用例说明:
- $$$a = [0, 7, 3, 1, 3, 7, 7]$$$ ;初始 MEX 为 $$$2$$$。
- $$$a = [0, \color{red}{2}, 3, 1, 3, 7, 7]$$$ ;新的 MEX 为 $$$4$$$。
- $$$a = [0, 2, 3, 1, \color{红色}{4}, 7, 7]$$$ ;新的 MEX 为 $$$5$$$。
- $$$a = [0, 2, 3, 1, \color{红色}{5}, 7, 7]$$$ ;新的 MEX 为 $$$4$$$。
- $$$a = [0, 2, 3, \color{红色}{4}, 5, 7, 7]$$$ ;新的 MEX 为 $$$1$$$。
- 最终数组是非递减的:$$$0 \le 2 \le 3 \le 4 \le 5 \le 7 \le 7$$$。