题目链接:http://codeforces.com/contest/1561/problem/E
首先发现如果偶数在奇数位置,奇数在偶数位置的话一定构造不出方案
考虑从大到小排序,因为只可以选择奇数前缀翻转,所以考虑每次将 \(i\) (奇数)和 \(i-1\) (偶数)放在一起构造
具体构造方案就是先将 \(i\) 翻转到 \(i-1\) 的左侧第一个位置,然后将序列整个翻转,这样就变成了 \(i-1,i\),然后再翻转 \(i\) 前缀,再翻转整个序列,\(i-1,i\) 就一起排好序了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2050;
int T, n, m;
int a[maxn];
vector<int> ans;
void rev(int x){
for(int i = 1 ; i <= x/2 ; ++i){
swap(a[i], a[x-i+1]);
}
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
int main(){
T = read();
while(T--){
ans.clear();
n = read(); m = 0;
for(int i = 1 ; i <= n ; ++i) a[i] = read();
int flag = 1;
for(int i = 1 ; i <= n ; ++i){
if((a[i] & 1) != (i & 1)){
flag = 0;
printf("-1\n");
break;
}
}
if(!flag) continue;
for(int i = n ; i >= 3 ; i -= 2){
int p1, p2;
for(int j = 1 ; j <= i ; ++j){
if(a[j] == i) p1 = j;
if(a[j] == i-1) p2 = j;
}
ans.push_back(p1);
rev(p1);
for(int j = 1 ; j <= i ; ++j){
if(a[j] == i) p1 = j;
if(a[j] == i-1) p2 = j;
}
ans.push_back(p2-1);
rev(p2-1);
ans.push_back(i);
rev(i);
for(int j = 1 ; j <= i ; ++j){
if(a[j] == i) {
p1 = j;
break;
}
}
ans.push_back(p1);
rev(p1);
ans.push_back(i);
rev(i);
}
m = ans.size();
printf("%d\n", m);
if(m > 0){
for(int i = 0 ; i < m ; ++i){
printf("%d ", ans[i]);
} printf("\n");
}
}
return 0;
}