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
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;
    debug(n);

    vector<int> a(n);
    REP(i, n)
        cin >> a[i];
    debug(a);

    auto sorted = a;
    sort(sorted.begin(), sorted.end());
    REP(i, n)
        a[i] = int(lower_bound(sorted.begin(), sorted.end(), a[i]) - sorted.begin());
    debug(a);

    vector<vector<int>> ans;
    while (not is_sorted(a.begin(), a.end())) {
        vector<bool> vis(n);
        vector<int> left, right;
        auto add_swap = [&](int i, int j) {
            left.emplace_back(i);
            right.emplace_back(j);
        };
        function<void(vector<int>)> solve_cycle = [&](vector<int> v) {
            debug("solve_cycle", v);
            if (v.empty() or v.back() == -1)
                return;
            int x = 0;
            while (v[x] == -1)
                ++x;
            assert(x == 1);
            int other = ssize(v) - 1;
            debug(x, other);
            if (x == other)
                return;
            add_swap(v[x], v[other]);

            vector<int> rec_vec(v.begin() + 1, v.end() - 1);
            if (ssize(rec_vec)) {
                rec_vec[0] = -1;
                solve_cycle(rec_vec);
            }
        };
        REP(i, n) {
            if (vis[i] or a[i] == i)
                continue;
            int x = i;
            vector<int> ids;
            while (not vis[x]) {
                ids.emplace_back(x);
                vis[x] = true;
                x = a[x];
            }
            if (ssize(ids) < 2)
                continue;
            add_swap(ids[0], ids[1]);
            ids.erase(ids.begin());
            ids[0] = -1;
            solve_cycle(ids);
        }
        left.insert(left.end(), right.rbegin(), right.rend());
        debug(left);
        ans.emplace_back(left);
        const int s = ssize(left);
        REP(i, s / 2)
            swap(a[left[i]], a[left[s - 1 - i]]);
        debug(a);
    }

    cout << ssize(ans) << '\n';
#ifndef LOCAL
    for (auto v : ans) {
        cout << ssize(v) << '\n';
        for (auto e : v) {
            cout << e + 1 << ' ';
        }
        cout << '\n';
    }
#endif
}