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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main () {
	int n;
	scanf("%d", &n);
	vector<int> data;
	for (int i = 0; i < n; ++i) {
		int x;
		scanf("%d", &x);
		data.push_back(x);
	}
	vector<int> positions(3008, -1);
	for (int i = 0; i < n; ++i) {
		positions[data[i]] = i;
	}
	sort(data.begin(), data.end());
	vector<int> v(n + 1, 0);
	for (int i = 0; i < n; ++i) {
		v[positions[data[i]] + 1] = i + 1;
	}
	vector<vector<pair<int, int> > > res;
	while (true) {
		bool sorted = true;
		for (int i = 1; i < n; ++i) {
			if (v[i] > v[i + 1]) {
				sorted = false;
				break;
			}
		}
		if (sorted) {
			break;
		}
		vector<pair<int, int> > iter;
		vector<bool> done(n + 8, false);
		for (int i = 1; i <= n; ++i) {
			if (done[i]) {
				continue;
			}
			vector<int> cycle;
			cycle.push_back(i);
			int next = v[i];
			while (next != i) {
				cycle.push_back(next);
				next = v[next];
			}
			for (int j = 0; j < cycle.size(); ++j) {
				done[cycle[j]] = true;
			}
			if (cycle.size() == 1) {
				continue;
			}
			if (cycle.size() == 2) {
				iter.push_back(make_pair(cycle[0], cycle[1]));
				continue;
			}
			int l = 1;
			int h = cycle.size() - 1;
			while (l < h) {
				iter.push_back(make_pair(cycle[l], cycle[h]));
				++l;
				--h;
			}
		}
		for (int i = 0; i < iter.size(); ++i) {
			int tmp = v[iter[i].first];
			v[iter[i].first] = v[iter[i].second];
			v[iter[i].second] = tmp;
		}
		res.push_back(iter);
	}
	printf("%d\n", res.size());
	for (int i = 0; i < res.size(); ++i) {
		printf("%d\n", 2 * res[i].size());
		for (int j = 0; j < res[i].size(); ++j) {
			printf("%d ", res[i][j].first);
		}
		for (int j = res[i].size() - 1; j >= 0; --j) {
			printf(j ? "%d " : "%d\n", res[i][j].second);
		}
	}
	return 0;
}