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
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <list>
#include <unordered_set>
#include <stack>


std::unordered_map<int, int> make_mapping(const std::vector<int>& input) {
    std::vector<int> sorted = input;
    std::stable_sort(sorted.begin(), sorted.end());

    std::unordered_map<int, int> map;
    for (int item : input) {
        map.insert({item, std::lower_bound(sorted.begin(), sorted.end(), item) - sorted.begin()});
    }

    return map;
}


std::vector<std::vector<int>> find_cycles(const std::vector<int>& input, const std::unordered_map<int, int>& map) {
    std::unordered_set<int> not_finished;

    for (int i = 0; i < input.size(); ++i) {
        not_finished.insert(i);
    }

    std::vector<std::vector<int>> all_cycles;
    std::vector<int> cycle;
    while (!not_finished.empty()) {
        cycle = {};

        int index = *not_finished.begin();

        while (not_finished.count(index)) {
            cycle.push_back(index);
            not_finished.erase(index);

            index = map.at(input[index]);
        }

        if (cycle.size() == 1) {
            continue;
        }

        all_cycles.push_back(cycle);
    }

    return all_cycles;
}


int main() {
    std::vector<int> input {};

    // Load Input Array
    int input_size;
    std::string temp_str;
    std::cin >> input_size;

    for (int i = 0; i < input_size - 1; ++i) {
        std::getline(std::cin, temp_str, ' ');
        input.push_back(std::stoi(temp_str));
    }

    std::getline(std::cin, temp_str, '\n');
    input.push_back(std::stoi(temp_str));


    // Solve
    std::vector<std::vector<int>> rounds {};
    auto mapping = make_mapping(input);

    while (true) {
        auto cycles = find_cycles(input, mapping);

        if (cycles.empty()) {
            break;
        }

        std::vector<int> round {};
        std::stack<int> round_end {};

        for (auto &cycle: cycles) {
            for (int i = 0; i < cycle.size() - 1; i += 2) {
                int &from = cycle[i], &to = cycle[i + 1];

                round.push_back(from);
                round_end.push(to);

                std::swap(input[from], input[to]);
            }
        }

        while (!round_end.empty()) {
            round.push_back(round_end.top());
            round_end.pop();
        }

        rounds.push_back(round);
    }


    // Echo solution
    std::cout << rounds.size() << '\n';

    for (auto& round : rounds) {
        std::cout << round.size() << '\n';

        for (auto& item : round) {
            std::cout << item + 1 << ' ';
        }

        std::cout << '\n';
    }

    return 0;
}