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

const int N = 3005;
int n, t[N];
vector<int> sL, sP;

vector< vector<int> > odp;

pair<int, int> tp[N];

int znajdz_id(int x){
    for(int i = 1 ; i <= n ; i++){
        if(t[i] == x)
            return i;
    }
    return -1;
}

void wypisz(){
    // cout <<" KONIEC SERI: ";
    vector<int> temp;
    for(int k = 0 ; k < sL.size() ; k++){
        // cout << sL[k]<<" ";
        temp.push_back(sL[k]);
    }
    for(int k = sP.size() - 1 ; k >= 0 ; k--){
        // cout << sP[k] <<" ";
        temp.push_back(sP[k]);
    }
    if(temp.size() > 0 )
        odp.push_back(temp);
    // cout <<"\n";
    sP.clear();
    sL.clear();
}

bool czyMoznaDodac(int x, int y){
    bool mozna = true;
    for(int k = 0 ; k < sL.size() ; k++){
        if(x == sL[k] || y == sL[k])
            mozna = false;
    }
    for(int k = 0 ; k < sP.size() ; k++){
        if(x == sP[k] || y == sP[k])
            mozna = false;
    }
    return mozna;
}

int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        cin >> t[i];
        tp[i] = {t[i], i};
    }
    sort(tp + 1, tp + n + 1);
    for(int i = 1 ; i <= n ; i++){
        int id = tp[i].second;
        t[id] = i; 
    }
    for(int elo = 1 ; elo <= 1000 ; elo++){
        for(int i = 1 ; i <= n ; i++){
            //chcemu tutaj dac i, -> znajdz takie j, że t[j] = i to jest nasz swap
            int id_i = znajdz_id(i);
            if(id_i != i){
                if(czyMoznaDodac(i, id_i)){
                    swap(t[i], t[id_i]);
                    sL.push_back(i);
                    sP.push_back(id_i);
                }   
            }
        }
        if(sL.size() == 0)
            break;
        wypisz();
    }

        printf("%ld\n", odp.size());
    for(auto x : odp){
        printf("%ld\n", x.size());
        for(auto y : x){
            printf("%d ",y);
        }
        printf("\n");
    }
    // for(int i = 1 ;  i <= n ; i++){
    //     cout << t[i] <<" ";
    // }
}