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

using namespace std;

vector<vector<int>> cycleDecomposition(vector<int> v){
	int n = v.size();
	vector<bool> used(n, false);
	vector<vector<int>> cycles;
	for(int i = 0; i < n; i++){
		if(v[i] != i && !used[i]){
			vector<int> xd;
			xd.push_back(i);
			used[i] = true;
			int current = v[i];
			while(current != i){
				used[current] = true;
				xd.push_back(current);
				current = v[current];
			}
			cycles.push_back(xd);
		}
	}
	return cycles;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n; cin>>n;
	vector<int> v(n);
	for(int i= 0; i < n; i++)cin>>v[i];
	//for(int i= 0; i < n; i++)v[i] = (i + 1) % n;
	vector<pair<int, int>> magic(n);
	for(int i= 0; i < n; i++){
		magic[i] = {v[i], i};
	}
	sort(magic.begin(), magic.end());
	for(int i= 0; i < n; i++){
		v[magic[i].second] = i;
	}
	//for(int i= 0; i < n; i++)cout<<v[i]<<"\n";
	
	/*for(auto t : cycles){
		for(auto x : t)cout<<x<<" ";
		cout<<"\n";
	}*/
	vector<vector<int>> orders;
	while(true){
		vector<vector<int>> cycles = cycleDecomposition(v);
		if(cycles.size() == 0)break;
		vector<pair<int, int>> swaps;
		for(int j = 0; j < cycles.size(); j++){
			int k = cycles[j].size();
			for(int i= 0; i < k - 1 - i; i++){
				swaps.push_back({cycles[j][i], cycles[j][k-1-i]});
			}
		}
		//for(auto p : swaps)cout<<p.first<<" "<<p.second<<"\n";
		//cout<<"\n\n\n";
		int m = swaps.size();
		for(int i= 0; i < m; i++){
			swap(v[swaps[i].first], v[swaps[i].second]);
		}
		vector<int> newOrder;
		for(int i= 0; i < m; i++){
			newOrder.push_back(swaps[i].first + 1);
		}
		for(int i = m-1; i >= 0; i--){
			newOrder.push_back(swaps[i].second + 1);
		}
		orders.push_back(newOrder);
	}
	cout<<orders.size()<<"\n";
	for(auto t : orders){
		cout<<t.size()<<"\n";
		for(auto x : t)cout<<x<<" ";
		cout<<"\n";
	}
	return 0;
}