这题的正解是的排序网络算法，感兴趣请移步官方题解，这里介绍一种能够通过的随机化算法。

先观察题目给出的第一种情况，原序列是降序的情况下，只需要一次操作即可完成排序。只用一次操作，就把逆序对最多的排列变成了逆序对最少的排列。如果我们继续顺着希望减少更多逆序对的思路，那么一种可行的办法是，交换尽量远的元素。也就是希望选到一对 有 ， 越大越好。

接下来我们考虑完全随机的数列。一开始，我们尽量远的数对，比如类似 地给出，经过一些这样的交换之后，每个数距离自己应在的位置变近，若仍然选择距离远的数对，能够交换的数对量将会变少。于是我们可以逐步降低给出的数对的距离。

经过以上的“逆序对贪心”的过程，我们可以把序列变得“接近”有序，即每个数都离原位置较近，但是不太能直接完成排序。那么就需要用剩下的一些次数进行类似冒泡的操作，完成排序的“最后一公里”。

什么，你说正确性？换个随机数种子都不一定过得去qwq

#include<bits/stdc++.h>
#include<random>
using namespace std;
#define ll long long
ll read() {
    ll x=0, f=1; char ch=' ';
    while(!isdigit(ch)) { ch=getchar(); if(ch=='-') f=-1; }
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-48), ch=getchar();
    return x*f;
}
random_device rd;
int n, res=200;
bool vis[10005];
void solve(int x, int y, int k) {
    for(int i=1;i<=k;i++) {
        memset(vis, 0, sizeof(vis));
        set<int> st;
        for(int j=0;j<n;j++) st.insert(j);
        printf("%d ", n/2);
        for(int j=0;j<n;j++) {
            if(vis[j]) continue;
            st.erase(j); vis[j]=1;
            int k=rd()%(x)+y;
            auto it=st.lower_bound(j+k);
            if(it==st.end()) --it;
            vis[*it]=1; 
            printf("%d %d ", j, *it);
            st.erase(it);
            if(st.size()<2) break;
        }
            printf("\n");
    }
    res-=k;
}
int main() {
 	mt19937 engine(103);
	//freopen("test.out", "w", stdout);
    cin>>n;
    if(n==1) {
        cout<<0;
        return 0;
    }
    if(n==2) {
        cout<<1<<endl;
        cout<<"1 0 1"<<endl;
        return 0;
    }
    cout<<res<<endl;
    if(n<=10) {
        for(int i=1;i<=200;i++) {
            if(i%2==1) {
                printf("%d ", n/2);
                for(int j=0;j+1<n;j+=2) printf("%d %d ", j, j+1);
            }
            else {
                printf("%d ", (n-1)/2);
                for(int j=1;j+1<n;j+=2) printf("%d %d ", j, j+1);
            }
            printf("\n");
        }
        return 0;
    }
    printf("%d ", n/2);
    for(int j=0;j<n-j-1;j++) printf("%d %d ", j, n-j-1);
    printf("\n");
    res--;
    
    if(n>300) {
        solve(1000, 300, 40);
    }
    
    if(n>200) {
        solve(200, 200, 30);
    }
    
    if(n>40) {
        solve(40, 40, 20);
    }
    
    solve(10, 10, 20);
    
    solve(10, 0, 20);
    
    //return 0;
    
    for(int i=1;i<=res;i++) {
        if(i%2==1) {
            printf("%d ", n/2);
            for(int j=0;j+1<n;j+=2) printf("%d %d ", j, j+1);
        }
        else {
            printf("%d ", (n-1)/2);
            for(int j=1;j+1<n;j+=2) printf("%d %d ", j, j+1);
        }
        printf("\n");
    }
    
}