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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> heights(n);
    vector<pair<int, int>> height_and_ind(n);
    for (int i = 0; i < n; ++i) {
        cin >> heights[i];
        height_and_ind[i]= make_pair(heights[i], i);
    }

    sort(height_and_ind.begin(), height_and_ind.end());

    for (int i = 0; i < n; ++i) {
        auto& [_, ind] = height_and_ind[i];
        heights[ind] = i;
    }

    vector<vector<int>> steps;

    while (true) {
        bool sorted = true;
        for (int i = 0; i < n; ++i) {
            if (heights[i] != i) {
                sorted = false;
                break;
            }
        }
        if (sorted) break;

        vector<bool> moved(n, false);
        vector<vector<int>> sub_arrays;
        vector<pair<int, int>> swaps;

        for (int i = 0; i < n; ++i) {
            if (moved[i]) continue;
            if (heights[i] == i) continue;

            auto& curr_sub = sub_arrays.emplace_back();
            int next = i;
            while (!moved[next]) {
                moved[next] = true;
                curr_sub.emplace_back(next);
                next = heights[next];
            }
        }

        for (auto& sub_array : sub_arrays) {
            if (sub_array.size() < 2) {
                continue;
            } else if (sub_array.size() == 2 || sub_array.size() == 3) {
                swaps.emplace_back(sub_array[0], sub_array[1]);
            } else {
                int mid_point = sub_array.size() / 2;
                int left = 0;
                int right = mid_point - 1;
                while (left < right) {
                    swaps.emplace_back(sub_array[left++], sub_array[right--]);
                }
                left = mid_point;
                right = sub_array.size() - 1;
                while (left < right) {
                    swaps.emplace_back(sub_array[left++], sub_array[right--]);
                }
            }
        }

        for (auto& [from, to] : swaps) {
            swap(heights[from], heights[to]);
        }

        auto& step = steps.emplace_back();;
        step.reserve(swaps.size() * 2);

        for (int i = 0; i < swaps.size(); ++i) {
            step.push_back(swaps[i].first);
        }

        for (int i = swaps.size()-1; i >= 0; --i) {
            step.push_back(swaps[i].second);
        }
    }

    cout << steps.size() << endl;
    for (auto& step : steps) {
        cout << step.size() << endl;
        for (auto ind : step) {
            cout << ind + 1 << " ";
        }
        cout << endl;
    }

    return 0;
}