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

int A[3005];
int B[3005];
int C[3005];
int L[3005];

bool cmp(int a, int b) {
    return A[a] < A[b];
}

std::vector<std::vector<std::pair<int,int>>> V;

void Swap(int v, int w) {
    V.back().push_back({v, w});
    std::swap(A[v], A[w]);
}

int len(int i) {
    int j = i;
    int l = 1;
    while (B[j] != i) {
        j = B[j];
        ++l;
    }
    j = i;
    L[j] = l;
    while (B[j] != i) {
        j = B[j];
        L[j] = l;
    }
    return l;
}

int next(int v, int k = 1) {
    while (k > 0) { v=B[v]; --k; }
    return v;
}
int prev(int v, int k = 1) {
    while (k > 0) { v=C[v]; --k; }
    return v;
}

void Split(int v) {
    int l = len(v);
    if (l == 2) {
        Swap(v, next(v));
    }
    int x = next(v);
    int y = prev(v);
    while (l > 4) {
        Swap(x, y);
        x = next(x);
        y = prev(y);
        Swap(x, y);
        x = next(x);
        y = prev(y);
        l-=4;
    }
    if (l >= 3) {
        Swap(x, y);
    }
}


int main() {
    std::ios_base::sync_with_stdio(0);
    int n;
    std::cin >> n;
    for (int i=0;i<n;++i) { std::cin >> A[i]; }
    do {
        for (int i=0;i<n;++i) { L[i]=0; }
        for (int i=0;i<n;++i) { B[i]=i; }
        std::sort(B, B+n, cmp);
        for (int i=0;i<n;++i) { C[B[i]]=i; }
        V.push_back({});
        for (int i=0;i<n;++i) if (L[i] == 0) Split(i);
    } while (!V.back().empty());
    V.pop_back();
    std::cout << V.size() << std::endl;
    for (auto& v : V) {
        std::cout << v.size()*2 << std::endl;
        for (auto&[a,b] : v)
            std::cout << a+1 << " ";
        std::reverse(v.begin(), v.end());
        for (auto&[a,b] : v)
            std::cout << b+1 << " ";
        std::cout << std::endl;
    }
    return 0;
}