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
#include <bits/stdc++.h>
using namespace std;
#pragma GCC maksuje_zadania_na_essie("pot200");

constexpr int MAX_N = 1e5 + 1;

pair<int,int> heights[MAX_N];
int ptr[MAX_N], vis[MAX_N];

vector<vector<pair<int,int>>> decompose_cycle(const vector<int> &cycle) {

	static vector<bool> is_resolved(MAX_N);
	vector<vector<pair<int,int>>> results;
	vector<int> unresolved;

	for(int c : cycle)
		unresolved.push_back(c);

	while(unresolved.size() > 1) {
		vector<pair<int,int>> result;
		for(int i = 0; i < unresolved.size()-1; i += 2) {
			is_resolved[unresolved[i]] = 1;
			result.push_back({ unresolved[i], unresolved[i+1] });
		}
		results.push_back(result);
		vector<int> new_unresolved;
		for(int i = 0; i < unresolved.size(); i++) {
			if(!is_resolved[unresolved[i]]) 
				new_unresolved.push_back(unresolved[i]);
		}
		unresolved = new_unresolved;
	}

	return results;

}

void find_cycle_nodes(int v, vector<int> &dest) {
	if(vis[v]) return;
	vis[v] = 1; dest.push_back(v);
	find_cycle_nodes(ptr[v], dest);
}

int main() {

	cin.tie(0)->sync_with_stdio(false);
	int n; cin >> n;

	for(int i = 0; i < n; i++) {
		cin >> heights[i].first;
		heights[i].second = i;
	}

	sort(heights, heights+n);

	for(int i = 0; i < n; i++) {
		ptr[heights[i].second] = i;
	}

	vector<vector<int>> cycles;

	for(int i = 0; i < n; i++) {
		if(vis[i]) continue;
		vector<int> new_cycle;
		find_cycle_nodes(i, new_cycle);
		cycles.push_back(new_cycle);
	}

	vector<vector<vector<pair<int,int>>>> decomposed_cycles;
	int max_layer = 0;

	for(const auto &cycle : cycles) {
		decomposed_cycles.push_back(decompose_cycle(cycle));
		max_layer = max(max_layer, int(decomposed_cycles.back().size()));
	}

	vector<deque<int>> queries;

	for(int i = 0; i < max_layer; i++) {
		deque<int> query;
		for(auto &decomposed_cycle : decomposed_cycles) {
			if(!decomposed_cycle.empty()) {
				for(auto &query_pair : decomposed_cycle.back()) {
					query.push_front(query_pair.first);
					query.push_back(query_pair.second);
				}
				decomposed_cycle.pop_back();
			}
		}
		queries.push_back(query);
	}

	cout << queries.size() << '\n';
	for(auto &query : queries) {
		cout << query.size() << '\n';
		while(!query.empty()) {
			cout << query.front()+1 << ' ';
			query.pop_front();
		}
		cout << '\n';
	}

}