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

int main()
{
	int n,a;
	cin >> n;
	pair <int ,int > A[n+4000];
	pair <int ,int > B[n+4000];
	int C[n+4000];
	for(int i=0;i<n;i++)
	{
		cin >> a;
		A[i].first = a;
		A[i].second = i+1;
		B[i].first = a;
		B[i].second = i+1;
	}
	
	sort(B,B+n);
	int licz=0;
	for(int i=0;i<n;i++)
	{
		if(A[i].second == B[i].second)
		{
			licz++;
		}
	}
	for(int i=0;i<n;i++)
	{
		C[i]=B[i].second;
	}
	
	int wyn=0;
	int odw[n+8];
	vector <vector<int>> v1;
	vector <vector<int>> v2;
	int ind=0;
	while(licz < n)
	{
		v1.push_back({});
		v2.push_back({});
		wyn++;
		for(int i=0;i<n;i++)
		{
			odw[i]=0;
			if(A[i].second == B[i].second)
		    {
			    odw[i]=1;
		    }
		}
		for(int i=0;i<n;i++)
		{
			int k = C[i];
			if(odw[i]==0 && odw[k-1]==0)
			{
				odw[i]=1;
				odw[k-1]=1;
				v1[ind].push_back(i+1);
				v2[ind].push_back(k);
				swap(A[i],A[k-1]);
			}
		}
		licz=0;
		for(int i=0;i<n;i++)
		{
			if(A[i].second == B[i].second)
		    {
			    licz++;
		    }
		}
		ind++;
		/*for(int i=0;i<n;i++)
		{
			cout << A[i].first << " " << A[i].second << "   " << B[i].first <<  " " << B[i].second << "\n";
		}
		cout << "\n\n";*/
	}
	
	cout << v1.size() << "\n";
	for(int i=0;i<v1.size();i++)
	{
		cout << v1[i].size()*2 << "\n";
		for(int j=0;j<v1[i].size();j++)
		{
			cout << v1[i][j] <<  " ";
		}
		for(int j=v2[i].size()-1;j>=0;j--)
		{
			cout << v2[i][j] <<  " ";
		}
		cout << "\n";
	}
	return 0;
}