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
#include<bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.in", "r", stdin);
    vector<int> tab;
    int n;
    cin>>n;
    int a;
    vector<int> stab;
    for(int i=0; i<n; i++){
        cin>>a;
        tab.push_back(a);
        stab.push_back(a);
    }
    sort(stab.begin(), stab.end());
    map<int,int> pozycje;
    for(int i=0; i<n; i++){
        pozycje[tab[i]]=i;
    }
    int w=0;
    vector<vector<int>> wyn;
    int ind=0;
    while (w!=tab.size()){
        w=0;
        vector<int> zmiany;vector<int> zmiany2;
        vector<bool> odw(n,false);
        // for(int i=0; i<n; i++){
        //     odw[i]=false;
        // }
        for(int i=0; i<n; i++){
            if(tab[i]==stab[i]){
                w++;
            }
            else{
                if(odw[i] or odw[pozycje[stab[i]]]) continue;
                odw[i]=true;
                odw[pozycje[stab[i]]]=true;
                zmiany.push_back(i);
                zmiany2.push_back(pozycje[stab[i]]);
                // int tmp=pozycje[tab[i]];
                swap(pozycje[tab[i]],pozycje[stab[i]]);
                // pozycje[stab[i]]=tmp;
                swap(tab[i],tab[pozycje[tab[i]]]);
            }   
        }
        if(zmiany.size()!=0){
            wyn.push_back({});
            // cout<<zmiany.size()+zmiany2.size()<<"\n";
            
            for(int i=0;i<zmiany.size(); i++){
                wyn[ind].push_back(zmiany2[i]+1);
            }
            
            for(int i=zmiany.size()-1; i>=0; i--){
                wyn[ind].push_back(zmiany[i]+1);
            }
            // cout<<"\n";
        }
        ind++;
    }
    // cout<<"JESTEM";
    cout<<wyn.size()<<"\n";
    for(int i=0; i<wyn.size(); i++){
        cout<<wyn[i].size()<<"\n";
        for (auto e:wyn[i]) cout<<e<<" ";
        cout<<"\n";
    }
    // if(w==tab.size()){ cout<<0; return 0;}
    return 0;
}