Codeforces Round #773 (Div. 2) D

• 首先每个数都必须出现偶数次才有可能找得到答案

  假设x出现了奇数次

  • 若插入过程始终没x，则有一个x始终不能匹配
  • 若插入过程有x，因为每次插入都是偶数个x，所以仍然会有一个x不能匹配

• 通过插入的方式可以将某一段变为"倒序"：

  例如： . . . , x , y , z , . . . . . . , x , y , z , x , x , . . . . . . , x , y , z , x , y , y , x , . . . . . . , x , y , z , x , y , z , z , y , x , . . . 最 终 序 列 变 成 了 ： [ . . . ] + [ ( x , y , z ) + ( x , y , z ) ] ) + [ z , y , x ] , . . . 因 为 [ ( x , y , z ) + ( x , y , z ) ] ) 可 以 不 用 理 了 ， 所 以 相 当 于 把 [ x , y , z ] 倒 序 了 ...,x,y,z,... \\ ...,x,y,z,x,x,... \\ ...,x,y,z,x,y,y,x,... \\ ...,x,y,z,x,y,z,z,y,x,... \\ 最终序列变成了：[...]+[(x,y,z)+(x,y,z)])+[z,y,x],... \\ 因为[(x,y,z)+(x,y,z)])可以不用理了，所以相当于把[x,y,z]倒序了 ...,x,y,z,......,x,y,z,x,x,......,x,y,z,x,y,y,x,......,x,y,z,x,y,z,z,y,x,...最终序列变成了：[...]+[(x,y,z)+(x,y,z)])+[z,y,x],...因为[(x,y,z)+(x,y,z)])可以不用理了，所以相当于把[x,y,z]倒序了

• 通过以上性质，从头到尾，每次找最近的一对数字的位置 i i i， j j j（ a i = a j a_i=a_j ai​=aj​），执行以下操作： a i , a i + 1 , . . . , a j − 1 , a j 翻 转 一 遍 为 ： a j − 1 , . . . , a i + 1 , a i , a j 再 翻 转 一 遍 ： a j , a i , a i + 1 , . . . , a j − 1 a_i,a_{i+1},...,a_{j-1},a_j \\ 翻转一遍为：a_{j-1},...,a_{i+1},a_{i},a_j \\ 再翻转一遍：a_j,a_i,a_{i+1},...,a_{j-1} ai​,ai+1​,...,aj−1​,aj​翻转一遍为：aj−1​,...,ai+1​,ai​,aj​再翻转一遍：aj​,ai​,ai+1​,...,aj−1​ 每次相当于在一个从头开始的数组操作，所以要记录他们的偏移量

#include <bits/stdc++.h>
#define ft first
#define sd second
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define seteps(N) fixed << setprecision(N)
#define endl "\n"
const int maxn = 6e5 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
int t, n, a[maxn];
int cntb, b[maxn];
bool vis[maxn];
vector <int> ans;
vector <pii> op;
map <int, int> mp;
int bas;
void init() { 
        
    mp.clear();
    ans.clear();
    op.clear();
    bas = cntb = 0;
    memset(vis, 0, sizeof(bool) * (n + 1));
}
bool pre() { 
         //检测是否合理
    for (int i = 1; i <= n; i++) mp[a[i]]++;
    for (auto np : mp)
        if (np.second & 1)
            return false;
    return true;
}
void cal(int num) { 
        
    int temp = num;
    for (int i = 1; i <= num; i++) { 
        
        op.push_back({ 
        bas + temp, b[i]});
        temp++;
    }
    bas += temp; //记录偏移
    ans.push_back(temp); //记录答案
}
void solve() { 
         //以下过程请自行手模一遍
    if (!pre()) { 
        
        puts("-1");
        return;
    }
    for (int i = 1, j, k; i <= n; i++) { 
        
        if (vis[i]) continue;
        for (j = i + 1; j <= n; j++) { 
        
            if (vis[j] || a[i] != a[j]) continue;
            cntb = 0;
            for (k = i; k <= j; k++)
                if (!vis[k])
                    b[++cntb] = a[k];
            break;
        }
        if (j == i + 1) { 
        
            vis[i] = vis[j] = true;
            bas += 2;
            ans.push_back(2);
            continue;
        }
        cal(cntb - 1);
        cntb = 0;
        for (k = j - 1; k >= i + 1; k--) 
            if (!vis[k])
                b[++cntb] = a[k];
        b[++cntb] = a[i]; b[++cntb] = a[i];
        cal(cntb);
        vis[i] = vis[j] = true;
        bas += 2;
        ans.push_back(2);
    }
    cout << op.size() << endl;
    for (auto np : op) cout << np.first << " " << np.second << endl;
    cout << ans.size() << endl;
    for (auto np : ans) cout << np << " ";
    cout << endl;
}
int main() { 
        
    cin >> t;
    while (t--) { 
        
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        init();
        solve();
    }
}