1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
const int MAXX=3005;
pair<int, int>tab[MAXX];
int uzylem[MAXX];
vector<int>G[2*MAXX];
int mapa[MAXX];
vector<pair<int, int>>z;
void f(int i, const int w){
    //cout<<"jebac"<<w+1<<" "<<i+1<<" ";
    if(i==w)return;
    int x=mapa[i];
    //cout<<x+1<<" ";
    //cout<<tab[x].second<<" "<<tab[w].second<<" : ";
    //mapa[x]->ktory element jest na pozycji x;
    if(uzylem[tab[x].first]==0){
        z.push_back({tab[x].second, tab[w].second});
        uzylem[tab[x].first]=1;
        uzylem[tab[w].first]=1;
        swap(mapa[tab[x].second], mapa[tab[w].second]);
        swap(tab[x].second, tab[w].second);
        return;
    }
    f(x, w);
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        tab[i]={a, i};
    }
    sort(tab, tab+n);
    for(int i=0;i<n;i++){
        //cout<<tab[i].first<<" ";
        mapa[tab[i].second]=i;
    }
    //cout<<"\n";
    int w=0;
    while(1){
        memset(uzylem, 0, sizeof uzylem);
        for(int i=0;i<n;i++){
            if(i==tab[i].second)continue;
            if(uzylem[tab[i].first]==1)continue;
            int x=mapa[i];
            if(mapa[x]==i){
                if(uzylem[tab[x].first]==0){
                    z.push_back({tab[x].second, tab[i].second});
                    uzylem[tab[x].first]=1;
                    uzylem[tab[i].first]=1;
                    swap(mapa[i], mapa[x]);
                    swap(tab[i].second, tab[x].second);
                }
                continue;
            }
           // cout<<"pizda";
            f(x, i);
        }
        if(z.size()==0)break;
        G[w].resize(z.size()*2);
        for(int i=0;i<z.size();i++){
            if(z[i].first>z[i].second)swap(z[i].second, z[i].first);
            //cout<<z[i].first<<" "<<z[i].second<<"\n";
            G[w][i]=z[i].first;
            G[w][z.size()*2-i-1]=z[i].second;
        }
        z.clear();
        w++;
    }
    cout<<w<<"\n";
    for(int i=0;i<w;i++){
        cout<<G[i].size()<<"\n";
        for(auto x : G[i]){
            cout<<x+1<<" ";
        }
        cout<<"\n";
    }
    return 0;
}