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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

struct Cycle {
    vi a;
    vi ind;
    int n;
    vector<vi> solve() {
        n = sz(a);
        vi mapper(a.begin(), a.end());
        sort(mapper.begin(), mapper.end());
        for (auto& x : a)
            x = lower_bound(mapper.begin(), mapper.end(), x) - mapper.begin();
        vi inv_a(n);
        for (int i = 0; i < n; i++)
            inv_a[a[i]] = i;
        vector<vi> res;
        while (!is_sorted(a.begin(), a.end())) {
            res.push_back({});
            vector<bool> used(n, false);
            for (int x = 0; x < n; x++) {
                if (a[x] == x) continue;
                if (!used[x] && !used[inv_a[x]]) {
                    res.back().push_back(x);
                    res.back().push_back(inv_a[x]);
                    used[x] = used[inv_a[x]] = true;
                }
            }
            for (int s = 0; s < sz(res.back()); s += 2) {
                swap(a[res.back()[s]], a[res.back()[s+1]]);
                inv_a[a[res.back()[s]]] = res.back()[s];
                inv_a[a[res.back()[s+1]]] = res.back()[s+1];
            }
        }
        return res;
    }

};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vi h(n);
    for (auto& x : h) cin >> x;
    vi mapper(h.begin(), h.end());
    sort(mapper.begin(), mapper.end());
    for (auto& x : h)
        x = lower_bound(mapper.begin(), mapper.end(), x) - mapper.begin();

    vector<Cycle> cycles;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        Cycle C;
        C.a.push_back(h[i]);
        C.ind.push_back(i);
        int j = h[i];
        while (!visited[j]) {
            visited[j] = true;
            C.a.push_back(h[j]);
            C.ind.push_back(j);
            j = h[j];
        }
        if ((int) C.a.size() > 1)
            cycles.push_back(C);
    }
    vector<vi> res;
    for (auto& C : cycles) {
        auto r = C.solve();
        for (int se = 0; se < sz(r); se++) {
            if (se >= sz(res)) res.push_back({});
            for (auto i : r[se])
                res[se].push_back(C.ind[i]);
        }
    }

    cout << sz(res) << '\n';
    for (auto swaps : res) {
        cout << sz(swaps) << '\n';
        for (int s = 0; s < sz(swaps); s += 2)
            cout << swaps[s] + 1 << ' ';
        for (int s = sz(swaps) - 1; s >= 0; s -= 2)
            cout << swaps[s] + 1 << ' ';
        cout << '\n';
    }

    return 0;
}