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
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

int tab[3009], col[3009], num[3009];
vector<int> wyn[3009], v, seq;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, a, b, c, x = 0;
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>tab[i];
		v.pb(tab[i]);
	}
	sort(v.begin(), v.end());
	for(int i=0; i<n; i++) num[v[i]] = i+1;
	for(int i=1; i<=n; i++) tab[i] = num[tab[i]];
	
	for(int i=1; i<=n; i++)
	{
		a = 1;
		seq.clear();
		for(int j=1; j<=n; j++) col[j] = 0;
		for(int j=1; j<=n; j++)
		{
			if(tab[j] != j && col[j] == 0)
			{
				v.clear();
				v.pb(j);
				col[j] = 1;
				a = 0;
				b = tab[j];
				while(col[b] == 0)
				{
					v.pb(b);
					col[b] = 1;
					b = tab[b];
				}
				b = 1;
				c = v.size()-1;
				while(c > b)
				{
					wyn[i].pb(v[b]);
					seq.pb(v[c]);
					swap(tab[v[b]], tab[v[c]]);
					b++;
					c--;
				}
				if(v.size() == 2)
				{
					wyn[i].pb(v[0]);
					seq.pb(v[1]);
					swap(tab[v[0]], tab[v[1]]);
				}
			}
		}
		if(a == 1) break;
		x = i;
		for(int j=seq.size()-1; j>=0; j--) wyn[i].pb(seq[j]);
	}	
	
	cout<<x<<"\n";
	for(int i=1; i<=n; i++)
	{
		if(wyn[i].size() == 0) break;
		cout<<wyn[i].size()<<"\n";
		for(int j=0; j<wyn[i].size(); j++) cout<<wyn[i][j]<<" ";
		cout<<"\n";
	}
	return 0;
}