[构造]Repetitions Decoding Codeforces1642D

Olya has an array of integers a1,a2,…,ana1,a2,…,an. 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 xx of even length 2k2k such that for each 1≤i≤k1≤i≤k the condition xi=xi+kxi=xi+k is satisfied.
• An array aa 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 cc and insert [c,c][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.

Input

Each test contains multiple test cases. The first line contains a single integer tt (1≤t≤300001≤t≤30000) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤5001≤n≤500).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109)  — the initial array.

It is guaranteed that the sum of n2n2 over all test cases does not exceed 250000250000.

Output

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−1.

Otherwise print the number of operations qq (0≤q≤2⋅n20≤q≤2⋅n2) that you want to do. Then print the descriptions of operations.

In each of the following qq lines print two integers pp and cc (1≤c≤1091≤c≤109), which mean that you insert the integer cc twice after pp elements of the array. If the length of the array is mm before the operation, then the condition 0≤p≤m0≤p≤m should be satisfied.

Then you should print any way to split the resulting array into tandem repeats. First, print a single integer dd, and then print a sequence t1,t2,…,tdt1,t2,…,td of even integers of size dd (d,ti≥1d,ti≥1). These numbers are the lengths of the subsegments from left to right.

Note that the size of the resulting array aa is m=n+2⋅qm=n+2⋅q. The following statements must hold:

• m=∑i=1dtim=∑i=1dti.
• For all integer ii such that 1≤i≤d1≤i≤d, the sequence al,al+1,…,aral,al+1,…,ar is a tandem repeat, where l=∑j=1i−1tj+1l=∑j=1i−1tj+1, r=l+ti−1r=l+ti−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.

Example

input

4
2
5 7
2
5 5
6
1 3 1 2 2 3
6
3 2 1 1 2 3

output

-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

题意： 给出一个长度为n的数组，每次操作可以选择任意一个位置并插入两个相同的数字，定义一个长度为2*t的平方串为前t个数字和后t个数字完全相同，例如1 1 2 1 1 2就是一个平方串，现在问你能否通过若干次操作得到一个串，这个串可以划分成若干个平方串。

分析： 如果数组中某数出现次数为奇数，那此时一定无解，因为无论作多少次操作该数出现次数仍然是奇数次，存在出现奇数次的数时是不可能符合题意的。而是否所有数出现次数都是偶数就一定有解呢？其实这时候按照下面的构造方法是一定有解的。遍历原数组，对于a[i]向后找第一个等于a[i]的位置j，此时依次在j位置后面添加a[i+1], a[i+2], ......, a[j-1]，也就是将a[i]到a[j-1]作为平方串中的第一段，第二段通过加数操作生成，以此类推直到遍历完整个数组，由于每个位置最多向后遍历n次，且每次最少也会前进一个位置，所以总时间复杂度为O(n^2)。虽然思路很简单，不过实现起来并不是很简单，里面有很多细节需要注意。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
int a[505];
vectorint, int>> ans1;
vector<int> ans2;
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		ans1.clear();
		ans2.clear();
		int n;
		scanf("%d", &n);
		map<int, int> mp;
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]); 
			mp[a[i]]++;
		}
		bool flag = false;
		for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
			if(it->second&1){
				flag = true;
				break;
			}
		}
		if(flag){
			puts("-1");
			continue;
		}
		int r = 0;
		for(int i = 1; i <= n; i++){
			int pos = -1;
			for(int j = i+1; j <= n; j++){
				if(a[i] == a[j]){
					pos = j;
					break;
				} 
			}
			if(pos == -1) break;
			int len = pos-i+1, cnt = 0;
			for(int j = i+1; j <= pos-1; j++){
				ans1.push_back(make_pair(r+len+cnt, a[j]));
				cnt++;
			}
			r += 2*(len-1);
			ans2.push_back(2*(len-1));
			vector<int> v;
			for(int j = i+1; j <= pos-1; j++) v.push_back(a[j]);
			reverse(v.begin(), v.end());
			for(int j = i+2; j <= pos; j++)
				a[j] = v[j-(i+2)];
			i = pos-(len-2);
		}
		printf("%d\n", ans1.size());
		for(int i = 0; i < ans1.size(); i++)
			printf("%d %d\n", ans1[i].first, ans1[i].second);
		printf("%d\n", ans2.size());
		for(int i = 0; i < ans2.size(); i++)
			printf("%d ", ans2[i]);
		puts("");
	}	
	return 0;
}