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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> g;
vector<vector<int>> wyn;

bool dodajRunde()
{
    vector<bool> z(n, false);
    vector<int> a, b;

    for (int ii=0; ii<n; ++ii)
    {
        if (z[ii] || g[ii]==ii)
            continue;

        vector<int> c;
        c.push_back(ii);
        for (int i=g[ii]; i!=ii; i=g[i])
            c.push_back(i);

        for (int i : c)
            z[i]=true;

        if (2 < c.size())
            c.erase(c.end()-1);

        for (int l=0, p=c.size()-1; l<p; ++l, --p)
        {
            int cl=c[l], cp=c[p];
            a.push_back(cl+1);
            b.push_back(cp+1);
            int x=g[cl];
            g[cl]=g[cp];
            g[cp]=x;
        }
    }

    if (a.empty())
        return false;
    for (int i=b.size()-1; 0<=i; --i)
        a.push_back(b[i]);
    wyn.push_back(a);
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n;
    vector<int> h;
    for (int i=0; i<n; ++i)
    {
        int a;
        cin>>a;
        h.push_back(a);
    }

    vector<int> s(h);
    sort(s.begin(), s.end());
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            if (h[i]==s[j])
                g.push_back(j);

//    for (int i=0; i<n; ++i)
//        cerr<<g[i]<<' ';

    while (dodajRunde())
        ;

    cout<<wyn.size()<<'\n';
    for (int i=0; i<wyn.size(); ++i)
    {
        cout<<wyn[i].size()<<'\n';
        for (int j=0; j<wyn[i].size(); ++j)
            cout<<wyn[i][j]<<' ';
        cout<<'\n';
    }

    return 0;
}