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
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<unordered_set>
#include<unordered_map>

using namespace std;

typedef vector<int> VI;
typedef long long LL;
typedef vector<LL> VLL;
typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define FOR(x, b, e) for(int x=b; x<=(e); ++x)
#define FORD(x, b, e) for(int x=b; x>=(e); --x)
#define REP(x, n) for(int x=0; x<(n); ++x)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define PB push_back
#define ST first
#define ND second

bool isSorted(VI &h) {
    REP(i, h.size() - 1) if (h[i] >= h[i + 1]) return false;
    return true;
}

void print(VPII &a) {
    bool isFirst = true;
    REP(i, a.size()) {
        if (!isFirst) cout << ' ';
        cout << a[i].ST + 1;
        isFirst = false;
    }
    FORD(i, a.size() - 1, 0) cout << ' ' << a[i].ND + 1;
    cout << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    VI h(n);
    REP(i, n) cin >> h[i];
    VI sorted(h);
    sort(sorted.begin(), sorted.end());
    unordered_map<int, int> shouldBe;
    unordered_map<int, int> ids;
    REP(i, n) shouldBe[sorted[i]] = ids[h[i]] = i;
    vector<VPII> result(0);
    while (!isSorted(h)) {
        VPII round;
        unordered_set<int> taken;
        REP(i, n) {
            int k = i;
            int j = shouldBe[h[k]];
            while (taken.count(j) == 0 && taken.count(k) == 0 && k != j) {
                round.PB({k, j});
                taken.insert(k);
                taken.insert(j);
                k = ids[sorted[k]];
                j = shouldBe[h[j]];
            }
        }
        REP(i, round.size()) {
            swap(h[round[i].ST], h[round[i].ND]);
            ids[h[round[i].ST]] = round[i].ST;
            ids[h[round[i].ND]] = round[i].ND;
        }
        result.PB(round);
        taken.clear();
        round.clear();
    }
    cout << result.size() << '\n';
    for (VPII r : result) {
        cout << 2 * r.size() << '\n';
        print(r);
    }
    return 0;
}