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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int position[3001];
int normalized[3001];
int reversed[3001];
vector<int> sorted;
vector<int> unsorted;

int main() {
    int n;
    int unordered = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int newnum;
        scanf("%d", &newnum);
        sorted.push_back(newnum);
        unsorted.push_back(newnum);
    }
    sort(sorted.begin(), sorted.end());
    for (int i = 0; i < sorted.size(); ++i) {
        position[sorted[i]] = i;
    }
    for (int i = 0; i < unsorted.size(); ++i) {
        normalized[i] = position[unsorted[i]];
        if (normalized[i] != i) {
            unordered += 1;
        }
    }
//    for (int i = 0; i < n; ++i) {
//        printf("%d ", normalized[i]);
//    }
    vector<vector<int>> answers;
    bool used[3001];
    while (true) {
        bool ordered = true;
        for (int i = 0; i < n; ++i) {
            reversed[normalized[i]] = i;
            if (normalized[i] != i) {
                ordered = false;
            }
            used[i] = false;
        }
        if (ordered) {
            break;
        }
        vector<int> endswaps;
        vector<int> startswaps;
        for (int i = 0; i < n; ++i) {
            if (used[i]) {
                continue;
            }
            if (normalized[i] != i) {
                int onefar = normalized[i];
                int twofar = normalized[normalized[i]];
                if (twofar == i) {
                    // swapping these 2 will put both into position
                    if (!used[i] && !used[onefar]) {
                        // the above 'if' should always be true
                        startswaps.push_back(onefar);
                        endswaps.push_back(i);
                        used[i] = true;
                        used[onefar] = true;
                    }
                } else {
                    // part of a 3+ cycle
                    // start with any onefar swap and then go 1 back from i and 1 forward from onefar
                    // until they're the same or
                    int leftidx = i;
                    int rightidx = onefar;
                    while (true) {
                        if (leftidx == rightidx) {
                            // end of odd cycle
                            break;
                        }
                        if (normalized[rightidx] == leftidx) {
                            // end of even cycle
                            break;
                        }
                        if (!used[leftidx] && !used[rightidx]) {
                            // the above 'if' should always be true but eh who knows
                            startswaps.push_back(leftidx);
                            endswaps.push_back(rightidx);
                            used[leftidx] = true;
                            used[rightidx] = true;
                        }
                        leftidx = reversed[leftidx];
                        rightidx = normalized[rightidx];
                    }
                }
            }
        }
        for (int i = 0; i < startswaps.size(); ++i) {
            int idx_1 = startswaps[i];
            int idx_2 = endswaps[i];
            int temp = normalized[idx_1];
            normalized[idx_1] = normalized[idx_2];
            normalized[idx_2] = temp;
        }
        for (int i = endswaps.size() - 1; i >= 0; --i) {
            startswaps.push_back(endswaps[i]);
        }
        answers.push_back(startswaps);
    }

    int ans_size = answers.size();
    printf("%d\n", ans_size);
    for (int i = 0; i < ans_size; ++i) {
        int swap_size = answers[i].size();
        printf("%d\n", swap_size);
        for (int j = 0; j < swap_size; ++j) {
            printf("%d ", answers[i][j] + 1);
        }
        printf("\n");
    }
    return 0;
}