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
//Jakub Nowak XIV LO Wroclaw
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int N = 3007;
int n;//1<=n<=3000
int H[N], P[N];
vector<deque<int>> O;//Odpowiedz

bool cmp(int a, int b) {
    return H[a]<H[b];
}

bool gotowe() {
    for(int i=1; i<=n; i++) if(P[i]!=i) return false;
    return true;
}

void dodaj_pare(int a, int b, deque<int> &Q) {
    swap(P[a],P[b]);
    Q.push_front(a);
    Q.push_back(b);
}

deque<int> ruch() {
    deque<int> Q;
    bool bylo[n+1];
    for(int i=0; i<=n; i++) bylo[i]=0;//bylo[i] = czy przeszlismy juz przez i-ta komurke
    for(int i=1; i<=n; i++) {
        if(bylo[i]) continue;
        vector<int> C={i};//cykl
        for(int j=P[i]; j!=i; j=P[j]) C.pb(j);//znajdowanie cyklu
        //-------------ogarnianie cyklu--------------
        for(auto u:C) bylo[u]=1;
        if(C.size()%2==1) C.pop_back();//odrzucenie niepotrzebnego
        for(int j=0; j<C.size()/2; j++) {//przejscie po parach
            dodaj_pare(C[j], C[C.size()-1-j], Q);
        }
        //-------------------------------------------
    }
    return Q;
}

void wypisz_P() {
    cout<<"\nP: ";
    for(int i=1; i<=n; i++) cout<<P[i]<<" ";
    cout<<"\n";
}

void rev() {
    int P2[n+1];
    for(int i=1; i<=n; i++) P2[P[i]]=i;
    for(int i=1; i<=n; i++) P[i]=P2[i];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) P[i]=i;
    for(int i=1; i<=n; i++) cin>>H[i];
    //wypisz_P();
    sort(P+1, P+n+1, cmp);
    rev();
    while(!gotowe()) {
        O.pb(ruch());
    }
    //--------------wypisywanie--------------
    cout<<O.size()<<"\n";
    for(auto Q:O) {
        cout<<Q.size()<<"\n";
        for(auto u:Q) cout<<u<<" ";
        cout<<"\n";
    }
}