CF1641B.Repetitions Decoding

Olya has an array of integers $a_1, a_2, \ldots, a_n$. She wants to split it into tandem repeats. Since it's rarely possible, before that she wants to perform the following operation several (possibly, zero) number of times: insert a pair of equal numbers into an arbitrary position. Help her!

More formally:

• A tandem repeat is a sequence $x$ of even length $2k$ such that for each $1 \le i \le k$ the condition $x_i = x_{i + k}$ is satisfied.
• An array $a$ could be split into tandem repeats if you can split it into several parts, each being a subsegment of the array, such that each part is a tandem repeat.
• In one operation you can choose an arbitrary letter $c$ and insert $[c, c]$ to any position in the array (at the beginning, between any two integers, or at the end).
• You are to perform several operations and split the array into tandem repeats or determine that it is impossible. Please note that you do not have to minimize the number of operations.

奥莉娅有一个整数数组 $a_1, a_2, \ldots, a_n$。她希望将该数组分割为若干个并列重复段（tandem repeat）。由于这通常无法直接实现，她决定先执行若干次（可能为零次）如下操作：在数组的任意位置插入一对相等的数。请你帮助她完成这一任务！

更形式化地定义如下：

• 一个并列重复段是指长度为偶数 $2k$ 的序列 $x$，满足对每个 $1 \le i \le k$，均有 $x_i = x_{i + k}$。
• 若能将数组 $a$ 划分为若干个连续子段（即子数组），且每个子段均为一个并列重复段，则称该数组可被划分为并列重复段。
• 每次操作中，你可以任选一个整数 $c$，并将 $[c, c]$ 插入到数组中的任意位置（开头、任意两个元素之间，或末尾）。
• 你需要执行若干次上述操作，使得最终数组可被划分为并列重复段；若不可能，请判定其不可行。注意：你无需最小化操作次数。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 30\,000$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 500$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the initial array.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $250\,000$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case print answer in the following format.

If you cannot turn the array into a concatenation of tandem repeats, print a single integer $-1$.

Otherwise print the number of operations $q$ ($0 \le q \le 2 \cdot n^2$) that you want to do. Then print the descriptions of operations.

In each of the following $q$ lines print two integers $p$ and $c$ ($1 \le c \le 10^9$), which mean that you insert the integer $c$ twice after $p$ elements of the array. If the length of the array is $m$ before the operation, then the condition $0 \le p \le m$ should be satisfied.

Then you should print any way to split the resulting array into tandem repeats. First, print a single integer $d$, and then print a sequence $t_1, t_2, \ldots, t_d$ of even integers of size $d$ ($d, t_i \ge 1$). These numbers are the lengths of the subsegments from left to right.

Note that the size of the resulting array $a$ is $m = n + 2 \cdot q$. The following statements must hold:

• $m = \sum\limits_{i = 1}^{d}{t_i}$.
• For all integer $i$ such that $1 \le i \le d$, the sequence $a_l, a_{l+1}, \ldots, a_r$ is a tandem repeat, where $l = \sum\limits_{j = 1}^{i - 1}{t_j} + 1$, $r = l + t_i - 1$.

It can be shown that if the array can be turned into a concatenation of tandem repeats, then there exists a solution satisfying all constraints. If there are multiple answers, you can print any.

对于每个测试用例，请按以下格式输出答案：

• 如果无法将数组变为若干个并置重复串（tandem repeat）的拼接，则输出单个整数 $-1$；
• 否则，首先输出你希望执行的操作次数 $q$（满足 $0 \le q \le 2 \cdot n^2$），然后输出 $q$ 行操作描述。

在接下来的 $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$，记 $l = \sum\limits_{j = 1}^{i - 1}{t_j} + 1$、$r = l + t_i - 1$，则子序列 $a_l, a_{l+1}, \ldots, a_r$ 是一个并置重复串。

可以证明：若原数组能被转化为若干并置重复串的拼接，则必存在满足所有约束条件的解。若存在多个合法答案，输出任意一个即可。

In the first test case, you cannot apply operations to the array to make it possible to split it into tandem repeats.

In the second test case the array is already a tandem repeat $[5, 5] = \underbrace{([5] + [5])}_{t_1 = 2}$, thus we can do no operations at all.

In the third test case, initially, we have the following array: $$[1, 3, 1, 2, 2, 3].$$ After the first insertion with $p = 1, c = 3$: $$[1, \textbf{3, 3}, 3, 1, 2, 2, 3].$$ After the second insertion with $p = 5, c = 3$: $$[1, 3, 3, 3, 1, \textbf{3, 3}, 2, 2, 3].$$ After the third insertion with $p = 5, c = 3$: $$[1, 3, 3, 3, 1, \textbf{3, 3}, 3, 3, 2, 2, 3].$$ After the fourth insertion with $p = 10, c = 3$: $$[1, 3, 3, 3, 1, 3, 3, 3, 3, 2, \textbf{3, 3}, 2, 3].$$ The resulting array can be represented as a concatenation of tandem repeats: $$\underbrace{([1, 3, 3, 3] + [1, 3, 3, 3])}_{t_1 = 8} + \underbrace{([3, 2, 3] + [3, 2, 3])}_{t_2 = 6}.$$

In the fourth test case, initially, we have the following array: $$[3, 2, 1, 1, 2, 3].$$ After the first insertion with $p = 0, c = 3$: $$[\textbf{3, 3}, 3, 2, 1, 1, 2, 3].$$ After the second insertion with $p = 8, c = 3$: $$[3, 3, 3, 2, 1, 1, 2, 3, \textbf{3, 3}].$$ After the third insertion with $p = 5, c = 3$ $$[3, 3, 3, 2, 1, \textbf{3, 3}, 1, 2, 3, 3, 3].$$ After the fourth insertion with $p = 6, c = 2$: $$[3, 3, 3, 2, 1, 3, \textbf{2, 2}, 3, 1, 2, 3, 3, 3].$$ After the fifth insertion with $p = 7, c = 1$: $$[3, 3, 3, 2, 1, 3, 2, \textbf{1, 1}, 2, 3, 1, 2, 3, 3, 3].$$ The resulting array can be represented as a concatenation of tandem repeats: $$\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}.$$

在第一个测试用例中，你无法对数组执行任何操作，使其能够被拆分为若干个并系重复（tandem repeat）。

在第二个测试用例中，该数组本身已是一个并系重复 $[5, 5] = \underbrace{([5] + [5])}_{t_1 = 2}$，因此我们完全无需执行任何操作。

在第三个测试用例中，初始数组为：

$$[1, 3, 1, 2, 2, 3].$$

第一次插入（$p = 1, c = 3$）后：

$$[1, \mathbf{3, 3}, 3, 1, 2, 2, 3].$$

第二次插入（$p = 5, c = 3$）后：

$$[1, 3, 3, 3, 1, \mathbf{3, 3}, 2, 2, 3].$$

第三次插入（$p = 5, c = 3$）后：

$$[1, 3, 3, 3, 1, \mathbf{3, 3}, 3, 3, 2, 2, 3].$$

第四次插入（$p = 10, c = 3$）后：

$$[1, 3, 3, 3, 1, 3, 3, 3, 3, 2, \mathbf{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$）后：

$$[\mathbf{3, 3}, 3, 2, 1, 1, 2, 3].$$

第二次插入（$p = 8, c = 3$）后：

$$[3, 3, 3, 2, 1, 1, 2, 3, \mathbf{3, 3}].$$

第三次插入（$p = 5, c = 3$）后：

$$[3, 3, 3, 2, 1, \mathbf{3, 3}, 1, 2, 3, 3, 3].$$

第四次插入（$p = 6, c = 2$）后：

$$[3, 3, 3, 2, 1, 3, \mathbf{2, 2}, 3, 1, 2, 3, 3, 3].$$

第五次插入（$p = 7, c = 1$）后：

$$[3, 3, 3, 2, 1, 3, 2, \mathbf{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}.$$