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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

struct Round {
    std::vector<int> left;
    std::vector<int> right;
};

int main() {
    std::ios::sync_with_stdio(false);

    int n; 
    std::vector<int> vals;

    std::cin >> n;
    vals.resize(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> vals[i];
    }

    std::vector<int> tmp_vec(vals);
    std::sort(vals.begin(), vals.end());

    std::map<int, int> transform;
    for (int i = 0; i < n; ++i) {
        transform[vals[i]] = i;
    }

    int to_sort = 0;
    for (int i = 0; i < n; i++) {
        vals[i] = transform[tmp_vec[i]];
        if (vals[i] != i) {
            to_sort++;
        }
    }

    // std::cout << "ini ";
    // for (int i = 0; i < n; ++i) {
    //     std::cout << vals[i] << " ";
    // }
    // std::cout << "\n";

    std::vector<Round> rounds;
    std::vector<bool> was_used;
    was_used.resize(n);
    
    while (to_sort > 0) {
        Round r;
        std::fill(was_used.begin(), was_used.end(), false);

        for (int i = 0; i < n; ++i) {
            
            if (vals[i] == i) {
                // std::cout << "w " << i << " wpisuje " << vals[i] << "\n";
                tmp_vec[i] = vals[i];
                continue;
            }
            if (was_used[i]) {
                continue;
            }
            if (was_used[vals[i]]) {
                tmp_vec[i] = vals[i];
                continue;
            }
            r.left.push_back(i);
            r.right.push_back(vals[i]);
            to_sort--;
            if (vals[vals[i]] == i) {
                to_sort--;
            }
            // std::cout << "w " << i << " wpisuje " << vals[vals[i]] << "\n";
            tmp_vec[i] = vals[vals[i]];
            // std::cout << "w " << vals[i] << " wpisuje " << vals[i] << "\n";
            tmp_vec[vals[i]] = vals[i];

            was_used[i] = true;
            was_used[vals[i]] = true;
        }
        for (int i = 0; i < n; ++i) {
            if (!was_used[vals[vals[i]]] && !was_used[i] && vals[vals[vals[i]]] != vals[i]) {

                r.left.push_back(i);
                r.right.push_back(vals[vals[i]]);
                was_used[vals[vals[i]]] = true;
                was_used[i] = true;

                tmp_vec[i] = vals[vals[vals[i]]];
                tmp_vec[vals[vals[i]]] = vals[i];
            }
        }
        
        // std::cout << "    ";
        // for (int i = 0; i < n; ++i) {
        //     std::cout << tmp_vec[i] << " ";
        // }
        // std::cout << "\n";
        rounds.push_back(r);
        std::swap(vals, tmp_vec);
    }

    // std::cout << "\n";std::cout << "\n";

    std::cout << rounds.size() << "\n";
    for (int i = 0; i < rounds.size(); ++i) {
        std::cout << rounds[i].left.size() * 2 << "\n";
        for (int j = 0; j < rounds[i].left.size(); ++j) {
            std::cout << rounds[i].left[j] + 1 << " ";
        }
        for (int j = rounds[i].right.size() - 1; j >= 0; --j) {
            std::cout << rounds[i].right[j] + 1 << " ";
        }
        std::cout << "\n";
    }

    std::cout.flush();

    return 0;
}