给定长为 (n) 的排列，操作至多 (6000) 次将 (a) 排序，每次操作选择子段 ([l,r])，将其重排为 (a_{l+1},a_{l+3},cdots,a_l,a_{l+2},cdots)。
(nle 3000)。
按照排序的套路，我们可以 ( exttt{for }i:n ightarrow 1) 将 (i) 复位。
可以发现我们可以操作 (O(log n)) 次将位置 (p) 的数移到最右边，总操作次数 (approx 35000)，不太优秀。
但是实际上比较优秀的是，将最右边的数移到位置 (p)，当 (p>frac n2) 时一次即可完成（操作子段 ([2p-n+1,n])），只需要 (log n-log p+O(1)) 步，它在平均情况下是 (O(1)) 的。
考虑倒着做这个过程。假设要找到若干个操作 (g_1,g_2,cdots,g_k)，使得 (e=g_kcirc g_{k-1}circcdotscirc g_1circ p)，那么 (g_1^{-1}circcdotscirc g_k^{-1}circ p^{-1}=e)，这就是刚才的问题，直接做就完了。
至于不是随机的怎么办呢，可以先随机跑个 (50) 次左右，操作次数就是 (2n+O(1)) 的。
#include<bits/stdc++.h>
using namespace std;
const int N = 3003, M = 15000;
int rd(){
int ch = getchar(), x = 0;
for(;ch < '0' || ch > '9';ch = getchar());
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
return x;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, _[N], a[N], b[N], ans[2][M], cnt;
void work(int l, int r){
ans[0][cnt] = l; ans[1][cnt++] = r;
memcpy(b+l, a+l, r-l+1<<2);
int p = l;
for(int i = l+1;i <= r;i += 2) a[i] = b[p++];
for(int i = l;i <= r;i += 2) a[i] = b[p++];
}
int main(){
n = rd();
for(int i = 1;i <= n;++ i) _[rd()] = i;
do { cnt = 0;
memcpy(a, _, n+1<<2);
for(int i = 0;i < 60;++ i){
int l = rng() % n + 1, r = rng() % n + 1;
if(l > r) swap(l, r);
if(l == r) continue;
work(l, r);
}
for(int i = n;i;-- i) if(a[i] != i){
int p = i;
while(a[p] != i) -- p;
while((p<<1)<=i) work(1, p<<=1);
if(p != i) work(2*p-i+1, i);
}
} while(cnt > 6000);
printf("%d
", cnt);
for(int i = cnt-1;~i;-- i) printf("%d %d
", ans[0][i], ans[1][i]);
}