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
129
130
131
132
133
134
#include <numeric>
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

/*
ZLE

5
2 0 4 1 3

1. Krok:
 2 <-> 4
 0 <-> 3

4 3 2 1 0

2. Krok:
Obrot wokol srodka
 4 <-> 0
 3 <-> 2

0 1 2 3 4
*/

struct td {
	int target;
	int height;
	bool dirty;
};

using vint = std::vector< int >;
using state_t = std::vector< td >;
using solution_t = std::vector< std::deque< int > >;

state_t prepare(vint const& heights) {
	vint sorted = heights;
	std::sort(sorted.begin(), sorted.end());

	state_t all;
	for(auto hei : heights) {
		int target = std::lower_bound(sorted.begin(), sorted.end(), hei) - sorted.begin();
		all.push_back({target, hei, false});
	}

	return all;
}

vint make_queue(state_t& ALL) {
	vint q;

	for(int i = 0; i < ALL.size(); ++i) {
		ALL[i].dirty = false;
		if(ALL[i].target != i) q.push_back(i);	
	}

	return q;
}

bool is_in_place(int k, state_t const& ALL) {
	return k == ALL[k].target;
}

bool is_clean(int k, state_t const& ALL) {
	if (ALL[k].dirty) return false;

	int target = ALL[k].target;
	if (ALL[target].dirty) return false;

	return true;
}

bool can_go(int k, state_t const& ALL) {
	if(is_in_place(k, ALL)) return false;
	return is_clean(k, ALL);
}

int put_in_place(state_t& ALL, int k, std::deque< int >& solpart) {
	int target = ALL[k].target;

	solpart.push_back(k);
	solpart.push_front(target);

	ALL[k].dirty = true;
	ALL[target].dirty = true;
	std::swap(ALL[k], ALL[target]);

	return ALL[k].target;
}

solution_t solve(vint const& heights) {
	solution_t solution;

	state_t ALL = prepare(heights);
	vint QUE = make_queue(ALL);

	while(0 < QUE.size()) {
		solution.push_back(std::deque< int >{});

		for(auto k : QUE) {
			if(is_in_place(k, ALL)) continue;

			if(! is_clean(k, ALL)) continue;

			int next = put_in_place(ALL, k, solution.back());
			while (can_go(next, ALL)) {
				next = put_in_place(ALL, next, solution.back());
			}
		}

		QUE = make_queue(ALL);
	}

	return solution;
}

int main() {
	int cnt; std::cin >> cnt;
	vint heights(cnt);
	for(int i = 0; i < cnt; ++i) { std::cin >> heights[i]; }

	solution_t solution = solve(heights);

	std::cout << solution.size() << "\n";
	for(auto& sol : solution) {
		size_t sz = sol.size();
		std::cout << sz << "\n";
		for(int i = 0; i < sz - 1; ++i) { std::cout << (sol[i] + 1) << " "; }
		std::cout << (sol[sz-1] + 1) << "\n";
	}

	return 0;
}