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


using namespace std;

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

    int n;
    cin >> n;

    pair <int, int> h[n];
    for (int i = 0; i < n; i++) {
        cin >> h[i].first;
        h[i].second = i;
    }

    sort(h, h + n);

    int tab[n];

    for (int i = 0; i < n; i++) {
        tab[h[i].second] = i;
    }

    int zmiana[n], n_zmian, x;
    for (int i = 0; i < n; i++) {
        zmiana[i] = -1;
    }
    
    vector < vector<int> > wynik;
    int wyczytani[n];

    while(true) {
        n_zmian = 0;

        for (int i = 0; i < n; i++) {
            x = i;
            while (tab[x] != x && zmiana[x] == -1 && zmiana[tab[x]] == -1) {
                zmiana[x] = tab[x];
                zmiana[tab[x]] = x;
                n_zmian++;

                x = tab[tab[x]];
            }
        }

        if (n_zmian == 0) break;

        x = 0;
        for (int i = 0; i < n; i++) {
            if (zmiana[i] != -1) {
                wyczytani[x] = i;
                wyczytani[n_zmian * 2 - 1 - x] = zmiana[i];

                swap(tab[i], tab[zmiana[i]]);

                zmiana[zmiana[i]] = -1;
                zmiana[i] = -1;
                
                x++;
            }
        }

        wynik.push_back (vector<int>(wyczytani, wyczytani + n_zmian * 2));
    }

    cout << wynik.size() << "\n";

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

    return 0;
}