Olya 有一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。她想将其分成串联重复。由于这种情况很少发生,因此在此之前她想多次(可能为零)执行以下操作:将一对相等的数字插入到任意位置。帮助她!
更正式地说:
- 串联重复是偶数长度 $$$2k$$$ 的序列 $$$x$$$,这样对于每个 $$$1 \le i \le k$$$ 满足条件 $$$x_i = x_{i + k}$$$。
- 如果您可以将数组 $$$a$$$ 拆分为多个部分,每个部分都是数组的子段,则可以将数组 $$$a$$$ 拆分为串联重复,这样每个部分都是串联重复。
- 在一个操作中,您可以选择任意字母 $$$c$$$ 并将 $$$[c, c]$$$ 插入到数组中的任何位置(开头、任意两个整数之间或末尾)。
- 您将执行多项操作并将数组拆分为串联重复,或者确定这是不可能的。请注意,您不必最小化操作次数。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 30\,000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 初始数组。
保证所有测试用例的$$$n^2$$$总和不超过$$$250\,000$$$。
输出
对于每个测试用例,按以下格式打印答案。
如果无法将数组转换为串联重复序列的串联,请打印单个整数 $$$-1$$$。
否则打印您想要执行的操作数 $$$q$$$ ($$$0 \le q \le 2 \cdot n^2$$$)。然后打印操作说明。
在下面的每一行 $$$q$$$ 中,打印两个整数 $$$p$$$ 和 $$$c$$$ ($$$1 \le c \le 10^9$$$),这意味着在数组的 $$$p$$$ 元素后面插入整数 $$$c$$$ 两次。如果运算前数组的长度为$$$m$$$,则应满足条件$$$0 \le p \le m$$$。
然后你应该打印任何方式将结果数组分割成串联重复。首先,打印单个整数 $$$d$$$,然后打印大小为 $$$d$$$ 的偶数整数的序列 $$$t_1, t_2, \ldots, t_d$$$ ($$$d, t_i \ge 1$$$)。这些数字是从左到右的子段的长度。
请注意,结果数组 $$$a$$$ 的大小为 $$$m = n + 2 \cdot q$$$。以下陈述必须成立:
- $$$m = \sum\limits_{i = 1}^{d}{t_i}$$$。
- 对于所有整数 $$$i$$$ 使得 $$$1 \le i \le d$$$,序列 $$$a_l, a_{l+1}, \ldots, a_r$$$ 是串联重复,其中 $$$l = \sum\limits_{j = 1}^{i - 1}{t_j} + 1$$$, $$$r = l + t_i - 1$$$。
可以证明,如果数组可以变成串联重复的串联,则存在满足所有约束的解。如果有多个答案,您可以打印任何一个。
示例
输入 #1
4 2 5 7 2 5 5 6 1 3 1 2 2 3 6 3 2 1 1 2 3
输出 #1
-1 0 1 2 4 1 3 5 3 5 3 10 3 2 8 6 5 0 3 8 3 5 3 6 2 7 1 4 2 6 6 2
注意
在第一个测试用例中,您无法对数组应用操作以使其能够将其拆分为串联重复。
在第二个测试用例中,数组已经是串联重复 $$$[5, 5] = \underbrace{([5] + [5])}_{t_1 = 2}$$$,因此我们根本无法执行任何操作。
在第三个测试用例中,最初,我们有以下数组: $$$$$$[1, 3, 1, 2, 2, 3].$$$$$$ 第一次插入 $$$p = 1, c = 3$$$ 后: $$$$$$[1, \textbf{3, 3}, 3, 1, 2, 2, 3].$$$$$$ 第二次插入 $$$p = 5, c = 3$$$: $$$$$$[1, 3, 3, 3, 1, \textbf{3, 3}, 2, 2, 3].$$$$$$ 第三次插入 $$$p = 5, c = 3$$$: $$$$$$[1, 3, 3, 3, 1, \textbf{3, 3}, 3, 3, 2, 2, 3].$$$$$$ 第四次插入后 $$$p = 10, c = 3$$$: $$$$$$[1, 3, 3, 3, 1, 3, 3, 3, 3, 2, \textbf{3, 3}, 2, 3].$$$$$$生成的数组可以表示为串联重复的串联: $$$$$$\underbrace{([1, 3, 3, 3] + [1, 3, 3, 3])}_{t_1 = 8} + \underbrace{([3, 2, 3] + [3, 2, 3])}_{t_2 = 6}.$$$$$$
在第四个测试用例中,最初,我们有以下数组: $$$$$$[3, 2, 1, 1, 2, 3].$$$$$$ 第一次插入 $$$p = 0, c = 3$$$ 后: $$$$$$[\textbf{3, 3}, 3, 2, 1, 1, 2, 3].$$$$$$ 第二次插入后 $$$p = 8, c = 3$$$: $$$$$$[3, 3, 3, 2, 1, 1, 2, 3, \textbf{3, 3}].$$$$$$ 第三次插入后 $$$p = 5, c = 3$$$ $$$$$$[3, 3, 3, 2, 1, \textbf{3, 3}, 1, 2, 3, 3, 3].$$$$$$ 第四次插入后 $$$p = 6, c = 2$$$: $$$$$$[3, 3, 3, 2, 1, 3, \textbf{2, 2}, 3, 1, 2, 3, 3, 3].$$$$$$ 之后第五次插入 $$$p = 7, c = 1$$$: $$$$$$[3, 3, 3, 2, 1, 3, 2, \textbf{1, 1}, 2, 3, 1, 2, 3, 3, 3].$$$$$$ 生成的数组可以表示为串联重复的串联: $$$$$$\underbrace{([3] + [3])}_{t_1 = 2} + \underbrace{([3, 2, 1] + [3, 2, 1])}_{t_2 = 6} + \underbrace{([1, 2, 3] + [1, 2, 3])}_{t_3 = 6} + \underbrace{([3] + [3])}_{t_4 = 2}.$$$$$$