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
/*
	Zadanie: Fotografia
	Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define DEB(x) cout << #x << ": " << x << '\n'

using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 7;
const int INF = 1e9 + 7;

deque<int> _sort(vector<int>& v)
{
	int n = v.size();
	vector<int> tmp = v;
	sort(tmp.begin(), tmp.end());
	vector<int> where(3001);
	vector<int> vis(n, 0);
	for (int i = 0; i < n; ++i)
		where[v[i]] = i;
	
	auto nb = [&](int a) { return where[tmp[a]]; };

	deque<int> res;
	for (int i = 0; i < n; ++i) {
		if (vis[i])
			continue;
		int a = i;
		vector<int> cyc;
		while (!vis[a]) {
			cyc.pb(a);
			vis[a] = true;
			a = nb(a);
		}
		if (cyc.size() == 1)
			continue;
		for (int j = 0; j < cyc.size() / 2; ++j) {
			res.push_back(cyc[j]);
			res.push_front(cyc[cyc.size() - j - 1]);
			swap(v[cyc[j]], v[cyc[cyc.size() - j - 1]]);
		}
	}
	return res;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n;
	cin >> n;
	vector<int> arr(n);
	for (auto& a : arr)
		cin >> a;

	vector<deque<int>> ans;
	while (!is_sorted(arr.begin(), arr.end())) {
		ans.pb(_sort(arr));
	}
	cout << ans.size() << '\n';
	for (auto v : ans) {
		cout << v.size() << '\n';
		for (auto p : v)
			cout << p + 1 << ' ';
		cout << '\n';
	}
	return 0;
}