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
#include <bits/stdc++.h>
using namespace std;
constexpr int LIM = 3000;
int tab[LIM + 10];
int con[LIM + 10];
bool vis[LIM + 10];
int main() {
    int n;
    scanf("%d", &n);
    vector<int>s;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &tab[i]);
        s.push_back(tab[i]);
    }
    sort(s.begin(), s.end());
    for(int i = 1; i <= n; i++) {
        con[s[i - 1]] = i;
    }
    for(int i = 1; i <= n; i++) {
        tab[i] = con[tab[i]];
    }
    vector<vector<int> >c;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            int akt = i;
            vector<int>tmp = {i};
            vis[akt] = 1;
            akt = tab[akt];
            while(!vis[akt]) {
                vis[akt] = 1;
                tmp.push_back(akt);
                akt = tab[akt];
            }
            if(tmp.size() > 1) {
                c.push_back(tmp);
            }
        }
    }
    vector<vector<int> >res;
    while(c.size()) {
        deque<int>q;
        vector<vector<int> >tmp;
        for(auto x : c) {
            vector<int>tmp2;
            if(x.size() == 2) {
                q.push_back(x[0]);
                q.push_front(x[1]);
            }
            else {
                for(int i = 0; i < (x.size() - 1) / 2; i++) {
                    q.push_back(x[i]);
                    q.push_front(x[x.size() - i - 2]);
                    tmp.push_back({x[i], x[x.size() - i - 1]});
                }
                if(!(x.size() & 1)) {
                    tmp.push_back({x[x.size() / 2 - 1], x[x.size() / 2]});
                }
            }
        }
        vector<int>tmp2;
        while(!q.empty()) {
            tmp2.push_back(q.back());
            q.pop_back();
        }
        res.push_back(tmp2);
        c = tmp;
    }
    printf("%ld\n", res.size());
    for(auto x : res) {
        printf("%ld\n", x.size());
        for(auto y : x) {
            printf("%d ", y);
        }
        puts("");
    }
}