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;

const int maxN = 3010;
int t[maxN];
int N;
vector<vector<int>> moves;

void scale() {
    map<int, int> sc;
    for (int i = 0; i < N; ++i)
        sc[t[i]];
    int nr = 0;
    for (auto &it : sc)
        it.second = nr++;
    for (int i = 0; i < N; ++i)
        t[i] = sc[t[i]];
}

void add_changes(vector<pair<int, int>> &changes) {
    if (changes.empty())
        return;

    moves.emplace_back();
    for (auto &it : changes) {
        moves.back().push_back(it.first);
        // swap(t[it.first], t[it.second]);
    }
    reverse(changes.begin(), changes.end());
    for (auto &it : changes)
        moves.back().push_back(it.second);
}

void printt() {
    printf("t: ");
    for (int i = 0; i < N; ++i)
        printf("%d ", t[i]);
    puts("");
}

void prepare() {
    vector<pair<int, int>> changes;
    vector<int> pos(N);

    for (int i = 0; i < N; ++i)
        pos[t[i]] = i;

    for (int i = 0; i < N; ++i) {
        if (pos[i] == i)
            continue;
        int a = i, b = pos[i];
        while (pos[b] != a) {
            int c = t[a];
            // printf("a = %d, looking at b=%d and c=%d\n", a, b, c);
            changes.emplace_back(pos[b], pos[c]);
            swap(t[pos[c]], t[pos[b]]);
            swap(pos[b], pos[c]);

            // printf("swapped %d with %d\n", b, c);
            // printt();

            a = c;
            b = pos[c];
        }
    }

    add_changes(changes);
}

void arrange() {
    vector<pair<int, int>> changes;
    for (int i = 0; i < N; ++i) {
        if (t[i] != i) {
            changes.emplace_back(i, t[i]);
            swap(t[i], t[t[i]]);
        }
    }
    add_changes(changes);
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", t + i);
    scale();
    // printt();
    prepare();
    // printt();
    arrange();
    // printt();
    printf("%lu\n", moves.size());
    for (auto &v : moves) {
        printf("%lu\n", v.size());
        for (int a : v)
            printf("%d ", a + 1);
        puts("");
    }
    return 0;
}