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

using namespace std;

typedef long long ll;

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

    int n;
    cin >> n;

    int h[n + 1], copy[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> h[i];    
        copy[i] = h[i];
    }
    sort(copy + 1, copy + n + 1);
    int sigma[n + 1];
    for (int i = 1; i <= n; i++) {
        sigma[i] = lower_bound(copy + 1, copy + n + 1, h[i]) - copy;
    }
    
    vector<vector<int>> cycles; 
    vector<int> jump;
    bool used[n + 1];
    for (int i = 1; i <= n; i++) {
        used[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            vector<int> v;
            v.push_back(i);
            used[i] = 1;
            int j = sigma[i];
            while (j != i) {
                v.push_back(j);
                used[j] = 1;
                j = sigma[j];
            }
            cycles.push_back(v);
            jump.push_back(1);
        }
    }

    vector<vector<int>> res; // operations
    bool done = 0;
    
    while (!done) {
        done = 1;
        vector<int> l, r;
        for (int i = 0; i < cycles.size(); i++) {
            if (jump[i] < cycles[i].size()) {
                for (int j = 0; (2 * j + 1) * jump[i] < cycles[i].size(); j++) {
                    l.push_back(cycles[i][2 * j * jump[i]]);
                    r.push_back(cycles[i][(2 * j + 1) * jump[i]]);
                } 
                jump[i] *= 2;
                if (jump[i] < cycles[i].size()) {
                    done = 0;
                }
            }
        }
        
        vector<int> v;
        for (int i = 0; i < l.size(); i++) {
            v.push_back(l[i]);
        }
        for (int i = r.size() - 1; i >= 0; i--) {
            v.push_back(r[i]);
        }
        if (v.size() > 0) {
            res.push_back(v);
        }
    }

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