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
#include <bits/stdc++.h>

using namespace std;

int n;
const int MAX_N = 3010;
vector<int> good_place;
int should_be_in[MAX_N];
vector<vector<int> > result;
int tab[MAX_N];
int where_is[MAX_N];

void exchange(int a, int b, vector<bool> &moved, vector<int> &bg, vector<int> &ed){
    moved[tab[a]] = true;
    moved[tab[b]] = true;
    bg.push_back(a+1);
    ed.push_back(b+1);
    where_is[tab[a]] = b;
    where_is[tab[b]] = a;
    swap(tab[a], tab[b]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> tab[i];
        good_place.push_back(tab[i]);
    }

    sort(good_place.begin(), good_place.end());
    for(int i=0; i<n; i++) should_be_in[good_place[i]] = i;
    for(int i=0; i<n; i++) where_is[tab[i]] = i;

    while(true){
        vector<bool> moved(MAX_N, false);
        vector<int> bg;
        vector<int> ed;
        for(int i=0; i<n; i++){
            if(should_be_in[tab[i]] != i && !moved[tab[i]] && !moved[tab[should_be_in[tab[i]]]]){
                // cout << "------ " << i+1 << " -------" << endl;
                // cout << "exchanging: " << i+1 << " " << should_be_in[tab[i]]+1 << endl;
                exchange(i, should_be_in[tab[i]], moved, bg, ed);

                int j = i;
                // cout << good_place[j] << " " << tab[j] << endl;
                while(good_place[j] != tab[j]){
                    int a = where_is[good_place[j]];
                    int move_to = should_be_in[tab[j]];
                    if(a == move_to) break;
                    // cout << "------ (j) " << j+1 << " -------" << endl;
                    // cout << "exchanging2: " << i+1 << " " << should_be_in[tab[i]]+1 << endl;
                    exchange(a, move_to, moved, bg, ed);
                    j = a;
                }
            }
        }
        vector<int> tmp_res;
        if(bg.size() == 0) break;
        for(int i=0; i<bg.size(); i++) tmp_res.push_back(bg[i]);
        for(int i=ed.size()-1; i>=0; i--) tmp_res.push_back(ed[i]);
        result.push_back(tmp_res);
    }

    cout << result.size() << endl;
    for(int i=0; i<result.size(); i++){
        cout << result[i].size() << endl;
        for(int j=0; j<result[i].size(); j++){
            cout << result[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}