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
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;

typedef long long lld;

constexpr int INF = (1<<30) - 1;
constexpr lld LINF = (1LL << 62) - 1;
constexpr int MAX_N = 1000000;

pair<int,int> t[MAX_N+9];
int last_update[MAX_N+9];
vector<int> circle;
vector<int> result[MAX_N+9][2];
int result_size;
int r;

void make_circle(int i, int start)
{
	last_update[i] = r;
	circle.push_back(i);
	if (start != t[i].ss)
	{
		make_circle(t[i].ss, start);
	}
}

void solve(int test_number)
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		t[i].ss = i;
		scanf("%d", &t[i].ff);
	}
	sort(t, t+n);
	bool finished = false;
	result_size = 0;
	r = 1;
	while (!finished)
	{
		finished = true;
		for (int i = 0; i < n; ++i)
		{
			if (last_update[i] < r && t[i].ss != i)
			{
				finished = false;
				circle.clear();
				make_circle(i, i);
				int j1 = 0;
				int j2 = circle.size()-1;
				while (j1 < j2)
				{
					result[result_size][0].push_back(t[circle[j1]].ss+1);
					result[result_size][1].push_back(t[circle[j2]].ss+1);
					swap(t[circle[j1]].ss, t[circle[j2]].ss);
					++j1;
					--j2;
				}
				circle.clear();
			}
		}
		result_size++;
		++r;
	}
	result_size--;
	printf("%d\n", result_size);
	for (int i = 0; i < result_size; ++i)
	{
		printf("%d\n", result[i][0].size()*2);
		for (size_t j = 0; j < result[i][0].size(); ++j)
		{
			printf("%d ", result[i][0][j]);
		}
		for (int j = result[i][0].size()-1; j >= 0; --j)
		{
			printf("%d ", result[i][1][j]);
		}
		printf("\n");
	}
}

int main()
{
	int test_number = 1;
	// scanf("%d", &test_number);
	for (int test_id = 0; test_id < test_number; ++test_id)
	{
		solve(test_number);
	}
}