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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// Kacper Orszulak
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <cassert>
#define fft(n) for (int i = 0; i < n; ++i) // Fast For Transform
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; cin >> n;
	vector<int> sorted_arr(n), arr(n);
	vector<int> wanted_pos(3000+1);
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
		sorted_arr[i] = arr[i];
	}
	sort(sorted_arr.begin(), sorted_arr.end());
	for (int i = 0; i < n; ++i) {
		wanted_pos[sorted_arr[i]] = i;
	}

	vector<vector<int>> rounds;
	while (true) {
		bool sorted = true;
		for (int i = 0; i < n-1; ++i) {
			if (arr[i] > arr[i+1]) {
				sorted = false;
				break;
			}
		}
		if (sorted)
			break;
		rounds.push_back({});
		vector<int> &cur_round = rounds.back();

		vector<int> al[2];
		al[0].assign(n, -1); // Outcoming
		al[1].assign(n, -1); // Incoming
		for (int i = 0; i < n; ++i) {
			const int j = wanted_pos[arr[i]];
			if (i == j)
				continue;
			al[0][i] = j;
			al[1][j] = i;

			// if (i == j || swapped[i] || swapped[j])
			// 	continue;
			// swapped[i] = true;
			// swapped[j] = true;
			// prefix.push(i);
			// suffix.push(j);
			// swap(arr[i], arr[j]);
		}

		vector<bool> swapped(n, false);
		queue<int> prefix;
		stack<int> suffix;
		for (int i = 0; i < n; ++i) {
			if (swapped[i])
				continue;

			int p, x;
			p = x = i;
			do {
				int y = al[0][x];
				if (y == -1 || y == p)
					y = al[1][x];
				if (y == -1 || y == p)
					break;

				if (!swapped[x] && !swapped[y]) {
					swapped[x] = true;
					swapped[y] = true;
					prefix.push(x);
					suffix.push(y);
					swap(arr[x], arr[y]);
				}

				p = x;
				x = y;
			} while (x != i);
		}

		// for (int i = 0; i < n; ++i) {
		// 	if (swapped[i] || (al[0][i] == -1 && al[1][i] == -1))
		// 		continue;
		// 	int j;
		// 	j = al[0][i];
		// 	if (j == -1 || swapped[j]) {
		// 		j = al[1][i];
		// 		if (j == -1 || swapped[j])
		// 			continue;
		// 	}

		// 	swapped[i] = true;
		// 	swapped[j] = true;
		// 	prefix.push(i);
		// 	suffix.push(j);
		// 	swap(arr[i], arr[j]);
		// }

		while (!prefix.empty()) {
			cur_round.push_back(prefix.front());
			prefix.pop();
		}
		while (!suffix.empty()) {
			cur_round.push_back(suffix.top());
			suffix.pop();
		}
	}

	cout << rounds.size() << '\n';
	for (const vector<int> &round : rounds) {
		cout << round.size() << '\n';
		for (const int e : round)
			cout << e+1 << ' ';
		cout << '\n';
	}

	return 0;
}