CF1641B Repetitions Decoding

Olya 有一个整数数组 $a_1, a_2, \ldots, a_n$。她想把它分割成“tandem repeat”。由于这通常很难做到，在此之前她可以进行若干次（可能为零次）如下操作：在任意位置插入一对相等的数字。请帮助她！ 更正式地说： - “tandem repeat” 是一个长度为 $2k$ 的序列 $x$，满足对于每个 $1 \le i \le k$，都有 $x_i = x_{i+k}$。 - 如果可以将数组 $a$ 分割成若干部分，每一部分都是数组的一个连续子段，且每一部分都是一个“tandem repeat”，则称数组 $a$ 可以被分割成“tandem repeat”。 - 每次操作你可以选择任意数字 $c$，并在数组的任意位置插入 $[c, c]$（可以在开头、任意两个整数之间或末尾插入）。 - 你需要进行若干次操作，并将数组分割成“tandem repeat”，或者判断无法做到。注意你不需要最小化操作次数。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 30000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 500$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示初始数组。 保证所有测试用例的 $n^2$ 之和不超过 $250000$。

对于每个测试用例，按如下格式输出答案。 如果无法通过操作将数组变为若干个“tandem repeat”的拼接，输出一个整数 $-1$。 否则，先输出你要进行的操作次数 $q$（$0 \le q \le 2n^2$）。接下来输出 $q$ 行，每行两个整数 $p$ 和 $c$（$1 \le c \le 10^9$），表示在数组前 $p$ 个元素后插入两个 $c$。如果操作前数组长度为 $m$，则 $0 \le p \le m$。 然后输出一种将最终数组分割成“tandem repeat”的方式。首先输出一个整数 $d$，然后输出 $d$ 个偶数 $t_1, t_2, \ldots, t_d$，表示从左到右每个子段的长度。 注意，最终数组长度 $m = n + 2q$。需满足以下条件： - $m = \sum\limits_{i = 1}^{d}{t_i}$。 - 对于所有 $1 \le i \le d$，序列 $a_l, a_{l+1}, \ldots, a_r$ 是一个“tandem repeat”，其中 $l = \sum\limits_{j = 1}^{i-1}{t_j} + 1$，$r = l + t_i - 1$。 可以证明，如果数组可以变为若干个“tandem repeat”的拼接，则一定存在满足所有约束的解。如果有多种答案，可以输出任意一种。

在第一个测试用例中，你无法通过操作使数组可以分割成“tandem repeat”。 在第二个测试用例中，数组本身就是一个“tandem repeat” $[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]$。最终数组可以表示为“tandem repeat”的拼接：$\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]$。最终数组可以表示为“tandem repeat”的拼接：$\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}$。 由 ChatGPT 4.1 翻译