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
#include<iostream>
#include<vector>
#include<set>
#include<deque>
#include<algorithm>
using namespace std;

bool unordered(vector<int> &vn, vector<int> &vs) {
    for (size_t i = 0; i < vn.size(); i++) {
        if (vn[i] != vs[i]) {
            return true;
        }
    }
    return false;
}

void simulate(vector<int> &vn, deque<int> &swaps) {
    int i = 0, j = swaps.size() - 1;
    while (i < j) {
        int t = vn[swaps[i]]; vn[swaps[i]] = vn[swaps[j]]; vn[swaps[j]] = t;
        i++;
        j--;
    }
}

int pos(vector<int> &vs, int e) {
    for (int i = 0; i < vs.size(); i++) {
        if (vs[i] == e) {
            return i;
        }
    }
    return 0;
}

int main() {
    int n;
    cin >> n;

    vector<int> vn, vs;
    for (int i = 0; i < n; i++) {
        int e;
        cin >> e;
        vn.push_back(e);
        vs.push_back(e);
    }
    vector<deque<int>> result;
    sort(vs.begin(), vs.end());
    while (unordered(vn, vs)) {
        set<int> visited;
        deque<int> swaps;
        for (int i = 0; i < n; i++) {
            if (vn[i] != vs[i]) {
                int k = i;
                while (visited.count(k) == 0 && visited.count(pos(vs, vn[k])) == 0) {
                    int j = pos(vs, vn[k]);
                    visited.insert(k);
                    visited.insert(j);
                    swaps.push_front(k);
                    swaps.push_back(j);
                    k = pos(vs, vn[j]);
                }
            }
        }
        if (!swaps.empty()) {
            simulate(vn, swaps);
            result.push_back(swaps);
        }        
    }

    cout << result.size() << endl;
    for (int i = 0; i < result.size(); i++) {
        deque<int> swaps = result[i];
        cout << swaps.size() << endl;
        for (int j = 0; j < swaps.size(); j++) {
            cout << (swaps[j] + 1) << " ";
        }
        cout << endl;
    }
    
}