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
//============================================================================
// Name        : 3c-fot.cpp
// Author      : poz
// Version     :
// Description : https://sio2.mimuw.edu.pl/c/pa-2022-1/p/fot/
//============================================================================
// https://stackoverflow.com/questions/44167728/sort-a-list-by-only-the-swapping-of-its-elements

#include <bits/stdc++.h>
using namespace std;
const int SIZE = 3001;

int h_array[SIZE];
int n;
bool changed[SIZE] = { false };

map<int, int> startPositionMap;
map<int, int> endPositionMap;

deque<int> round1;

void completeFor(int i) {

	int i_value = h_array[i];
	if (i_value == i) {
		return;
	}
	const int current_second_value = h_array[i_value];
	if (changed[current_second_value]) {
		return;
	}
	h_array[i_value] = i;
	int i_position = startPositionMap[i];
	h_array[i_position] = current_second_value;
	round1.push_front(i_position);
	round1.push_back(i_value);
	changed[i_position] = true;
	changed[i_value] = true;
	completeFor(i_position);
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	vector<int> hs(n);
	vector<int> ordered_hs(n);

	for (int i = 0; i < n; i++) {
		cin >> hs[i];
		ordered_hs[i] = hs[i];
	}
	sort(ordered_hs.begin(), ordered_hs.end());

	for (int i = 0; i < n; i++) {
		endPositionMap[ordered_hs[i]] = i + 1;
	}
	for (int i = 0; i < n; i++) {
		h_array[i + 1] = endPositionMap[hs[i]];
		startPositionMap[endPositionMap[hs[i]]] = i + 1;
	}



	for (int i = 1; i <= n; i++) {
		if (changed[i]) {
			continue;
		}
		int i_value = h_array[i];
		if (i_value == i) {
			continue;
		}
		if (changed[i_value]) {
			continue;
		}
		round1.push_front(i);
		round1.push_back(i_value);
		changed[i] = true;
		changed[i_value] = true;
		h_array[i] = h_array[i_value];
		h_array[i_value] = i_value;
		completeFor(i);

	}

	vector<deque<int>> queueList;
	if (round1.size() > 0) {
		queueList.push_back(round1);
	}

	deque<int> round2;
	set<int> processed;
	for (int i = 1; i <= n; i++) {
		if (processed.count(i) > 0) {
			continue;
		}
		int i_value = h_array[i];
		if (i == i_value) {
			continue;
		}
		h_array[i] = h_array[i_value];
		h_array[i_value] = i;
		round2.push_front(i);
		round2.push_back(i_value);
		processed.insert(i);
		processed.insert(i_value);
	}

	if (round2.size() > 0) {
		queueList.push_back(round2);
	}

	cout << queueList.size() << endl;
	for (auto dq : queueList) {
		cout << dq.size() << endl;
		for (auto pos : dq) {
			cout << pos << " ";
		}
		cout << endl;
	}

	return 0;
}