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 <bits/stdc++.h>
using namespace std;

map<int, int> sk;

int t[3005];

void printAns(vector<deque<int>> &ans) {
    cout << ans.size() << "\n";
    for (auto i : ans) {
        cout << i.size() << "\n";
        for (auto j : i) {
            cout << j << " ";
        }
        cout << "\n";
    }
}

int32_t main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        sk[t[i]] = 1;
    }

    int N = 0;
    for (auto &i : sk) {
        i.second = ++N;
    }

    for (int i = 1; i <= n; i++) {
        t[i] = sk[t[i]];
    }

    vector<deque<int>> ans;
    while (!is_sorted(t + 1, t + n + 1)) {
        vector<int> braned(n + 1, 0);
        deque<int> swaps;
        for (int i = 1; i <= n; i++) {
            // cerr << "AAAA";
            if (!braned[i]) {
                vector<int> vis(n + 1, 0);
                vector<int> cyc;
                int pos = i;
                while (!vis[pos]) {
                    cyc.push_back(pos);
                    vis[pos] = 1;
                    pos = t[pos];
                }

                if (cyc.size() == 1) continue;

                int j = 0, k = cyc.size() / 2;
                if (braned[cyc[k]] || braned[cyc[j]]) continue;
                swaps.push_front(cyc[j]);
                swaps.push_back(cyc[k]);
                swap(t[cyc[j]], t[cyc[k]]);
                braned[cyc[j]] = braned[cyc[k]] = 1;
                j = (j + 1) % cyc.size();
                k = (k - 1 + cyc.size()) % cyc.size();
                while (!braned[cyc[j]] && !braned[cyc[k]] && j != k) {
                    // cerr << "XD";
                    swaps.push_front(cyc[j]);
                    swaps.push_back(cyc[k]);
                    swap(t[cyc[j]], t[cyc[k]]);
                    braned[cyc[j]] = braned[cyc[k]] = 1;
                    j = (j + 1) % cyc.size();
                    k = (k - 1 + cyc.size()) % cyc.size();
                }

                j = cyc.size() / 2 + 1, k = cyc.size() - 1;
                while (!braned[cyc[j]] && !braned[cyc[k]] && j != k) {
                    // cerr << "XD";
                    swaps.push_front(cyc[j]);
                    swaps.push_back(cyc[k]);
                    swap(t[cyc[j]], t[cyc[k]]);
                    braned[cyc[j]] = braned[cyc[k]] = 1;
                    j = (j + 1) % cyc.size();
                    k = (k - 1 + cyc.size()) % cyc.size();
                }

                // for (auto i : swaps) cerr << i << " ";
                // cerr << "\n";

                // int best_j = -1, best_k = -1;
                // for (int j = 0; j < cyc.size(); j++) {
                //     for (int k = j + 1; k < cyc.size(); k++) {
                //         if (!braned[cyc[j]] && !braned[cyc[k]]) {
                //             if (min(k - j, (int)cyc.size() - (k - j)) >=
                //                 min(best_k - best_j, (int)cyc.size() - (best_k - best_j))) {
                //                 best_j = j;
                //                 best_k = k;
                //             }
                //         }
                //     }
                // }

                // if (best_j == -1) continue;

                // int idx_j = cyc[best_j], idx_k = cyc[best_k];
                // swaps.push_front(idx_j);
                // swaps.push_back(idx_k);
                // braned[idx_j] = braned[idx_k] = 1;
                // swap(t[idx_j], t[idx_k]);

                // for (int j = 1; j <= n; j++) {
                //     cerr << t[j] << " ";
                // }

                // cerr << "\n";
            }
        }
        ans.push_back(swaps);
        // printAns(ans);
        // return 0;
    }
    printAns(ans);
}