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
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

struct Graduates
{
	std::vector<long> h;
	std::vector<long> h_sorted;
	std::unordered_map<long, long> indexes_in_sorted;
	std::vector<std::vector<std::pair<long,long>>> changes;
	void prepare() {
		h_sorted = h;
		std::sort(h_sorted.begin(), h_sorted.end());
		for (long i = 0; i < h_sorted.size(); i++) {
			indexes_in_sorted[h_sorted[i]] = i;
		}
	}

	void addChanges() {
		std::unordered_set<long> used_indexes;
		std::vector<std::pair<long,long>> change;
		for (long i = 0; i < h.size(); ++i) {
			long j = indexes_in_sorted[h[i]];
			if (used_indexes.find(i) == used_indexes.end() && used_indexes.find(j) == used_indexes.end() && i != j) {
				used_indexes.insert(i);
				used_indexes.insert(j);
				change.push_back(std::pair<long,long>(i, j));
			}
		}
		applyChange(change);
		changes.push_back(change);
	}

	void applyChange(const std::vector<std::pair<long,long>> &change) {
		for (auto c : change) {
			std::swap(h[c.first], h[c.second]);
		}
	}

	void findChanges() {
		while (!std::is_sorted(h.begin(), h.end())) {
			addChanges();
		}
	}

	void printChanges() {
		std::cout << changes.size() << std::endl;
		for (auto &v : changes) {
			std::deque<long> result;

			for (auto p : v) {
				result.push_front(p.first + 1);
				result.push_back(p.second + 1);
			}

			std::cout << result.size() << std::endl;
			for (long i = 0; i < result.size(); i++) {
				std::cout << result[i];
				if (i < result.size() - 1) {
					std::cout << " ";
				}
			}
			std::cout << std::endl;
		}
	}
};

int main() {
	long n{};
	std::cin >> n;
	Graduates g;

	for (long i = 0; i < n; i++) {
		long tmp{};
		std::cin >> tmp;
		g.h.push_back(tmp);
	}
	g.prepare();

	g.findChanges();

	g.printChanges();
	return 0;
}