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
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

pair<int,int> t[4005];
int n, tab[3005], gdzie[3005];
bool dead[3005];
vector <list<int>> odp;

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i=1; i<=n; i++)
    {
        cin >> t[i].first;
        t[i].second=i;

    }
    sort(t+1, t+n+1);
    for (int i=1; i<=n; i++)
    {
        tab[t[i].second]=i;
        gdzie[i]=t[i].second;
    }

    // for (int i=1; i<=n; i++)
    // {
    //     cout << i << ' ' << tab[i] << '\n'; 
    // }

    for (; ;)
    {
        list<int> K;
        bool f=true;

        for (int i=1; i<=n; i++)
        {
            dead[i]=0;
            if (tab[i]!=i) 
                f=false;
        }
            
        if (f) 
            break;

        for (int i=1; i<=n; i++)
        {
            if (!dead[i])
            {
                dead[i]=1;
                vector <int> pom;
                pom.push_back(i);
                int a=tab[i];

                while (!dead[a])
                {
                    dead[a]=1;
                    pom.push_back(a);
                    a=tab[a];
                }
                
                if (pom.size()>1) 
                {
    
                    for (int j=0; j<(pom.size()/2); j++)
                    {
                        K.push_front(pom[j]);
                        K.push_back(pom[pom.size()-1-j]);
                        swap(tab[pom[j]], tab[pom[pom.size()-1-j]]);
                    }
                }
            }
        }

        odp.push_back(K);

    }

    cout << odp.size() << '\n';
    for (auto i : odp)
    {
        cout << i.size() << '\n';
        for(auto j: i)
        {
            cout << j << ' ';
        }
        cout << '\n';
    }

return 0;
}