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
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second

using namespace std;

int H[5000];
int R[5000];
bool vis[5000];

bool posortowane(int N){
	for(int i=1; i<=N; i++){
		if(R[i]!=i) return 0;
	}
	return 1;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie();
	int N;
	cin>>N;
	for(int i=1; i<=N; i++){
		cin>>H[i];
	}
	vector <pair<int,int> > vec;
	for(int i=1; i<=N; i++){
		vec.pb({H[i],i});
	}
	sort(vec.begin(),vec.end());
	for(int i=0; i<N; i++){
		R[vec[i].se]=i+1;
	}
	for(int i=1; i<=N; i++){
	//	cout<<R[i]<<" ";
	}
//	vector<pair<int,int> > srt;
	vector<vector<int> > inst; 
	int T=0;
	while(!posortowane(N)){
		vector<pair<int,int> > zamiany;
		vector <int> mik;
		vector <int> pom;
		T++;
		for(int i=1; i<=N; i++) vis[i]=0;
		for(int i=1; i<=N; i++){
			if(!vis[i]){
				pom.clear();
				pom.pb(i);
				vis[i]=1;
				int j=i;
				while(!vis[R[j]]){
					j=R[j];
					vis[j]=1;
					pom.pb(j);
				}
				for(int k=0; k<pom.size()-(pom.size()%2); k+=2){
					zamiany.pb({pom[k],pom[k+1]});
	//				cout<<"{"<<pom[k]<<","<<pom[k+1]<<"}\n";
				}
			}
		}
		for(int i=0; i<zamiany.size(); i++){
			mik.pb(zamiany[i].fi);
		}
		for(int i=zamiany.size()-1; i>=0; i--){
			mik.pb(zamiany[i].se);
		}
		inst.pb(mik);
		for(int i=0; i<zamiany.size(); i++){
			swap(R[zamiany[i].fi],R[zamiany[i].se]);
		}
	//	cout<<"--------\n";
		

	}

	cout<<T<<"\n";
	for(int i=0; i<inst.size(); i++){
		cout<<inst[i].size()<<"\n";
		for(int j=0; j<inst[i].size(); j++){
			cout<<inst[i][j]<<" ";
		}
		cout<<"\n";
	}




	return 0;
}