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
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,i;
	vector <vector<int>>result;
	vector <pair<int,int>> zamiana;
	scanf("%d",&n);
	int arr[n];
	int tmp[n];
	bool used[n];
	for(i=0;i<n;i++){
		scanf("%d",&arr[i]);
		tmp[i]=arr[i];
	}
	sort(tmp,tmp+n);
	for(i=0;i<n;i++)
		arr[i]=lower_bound(tmp,tmp+n,arr[i])-tmp;
	while(true){
		for(i=0;i<n;i++)
			used[i]=false;
		zamiana.clear();
		for(i=0;i<n;i++){
			if(arr[i]!=i){
				if(!used[i] && !used[arr[i]]){
					zamiana.push_back({i,arr[i]});
					used[arr[i]]=true;
					used[i]=true;
				}
			}
		}
		if(zamiana.size()==0)
			break;
		result.push_back({});
		for(i=0;i<(int)zamiana.size();i++)
			result.back().push_back(zamiana[i].first);
		for(i=zamiana.size()-1;i>=0;i--)
			result.back().push_back(zamiana[i].second);
		for(auto ai:zamiana)
			swap(arr[ai.first],arr[ai.second]);
	}
	printf("%d\n",(int)result.size());
	for(auto v:result){
		printf("%d\n",(int)v.size());
		for(auto ai:v)
			printf("%d ",ai+1);
		printf("\n");
	}
	return 0;
}