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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

typedef std::pair<int,int> IntPair;

void swap(std::vector<int> & v, int a, int b){
	int t = v[a];
	v[a] = v[b];
	v[b] = t;
}

void getSwapsFromCycle(std::vector<int> & cycle, int b, int e, std::vector<IntPair> & lastSwaps){
	if (b >= e || cycle.empty()) return;

//	printf("SWAP %d (%d) %d (%d) \n", b, cycle[b], e, cycle[e]);
	lastSwaps.push_back(IntPair(cycle[b], cycle[e]));

	getSwapsFromCycle(cycle, b + 1, e - 1, lastSwaps);
}

void findCycles(std::vector<int> & toShift, std::vector<std::vector<IntPair> > & allInversions){
	std::set<int> touched;
	allInversions.push_back(std::vector<IntPair>());
	for(int i = 1; i < (int)toShift.size(); ++i){
		if (toShift[i] != i && touched.find(i) == touched.end()){
			std::vector<int> cycle;
			int next = i;
			while(touched.find(next) == touched.end()){
				cycle.push_back(next);
				touched.insert(next);
				next = toShift[next];
			}
//			printf("CYCLE :\n");
//			for(int j = 0; j < (int)cycle.size(); ++j){
//				printf("%d ", cycle[j]);
//			}
//
//			printf("\n");
			if ( cycle.size() == 2){
//				printf("SWAP %d (%d) %d (%d) \n", 0, cycle[0], 1, cycle[1]);
				allInversions.back().push_back(IntPair(cycle[0], cycle[1]));
			} else {
				getSwapsFromCycle(cycle, 1, cycle.size() - 1, allInversions.back());// opuszczamy pierwszy
			}

//			printf("KONIEC SWAPOW ================================\n");

		}
	}
	for(int j = 0; j < (int)allInversions.back().size(); ++j){
//		printf("SWAP [%d] [%d]  \n", allInversions.back()[j].first, allInversions.back()[j].second);
		swap(toShift, allInversions.back()[j].first, allInversions.back()[j].second);
	}
}

int main(){
	int n;
	scanf("%d", &n);
	std::vector<int> toShift(n + 1, 0);
	std::vector<int> toSort;
	std::map <int,int> posMapping;
	for(int i = 1; i <= n; ++i){
		scanf("%d", &toShift[i]);
		toSort.push_back(toShift[i]);
	}
	std::sort(toSort.begin(), toSort.end());
	for(int i = 0; i < n; ++i){
		posMapping[toSort[i]] = i + 1;
	}
	for(int i = 1; i <= n; ++i){
		toShift[i] = posMapping[toShift[i]];
	}
//	for(int i = 1; i <= n; ++i){
//		printf("%d ", toShift[i]);
//	}
//	printf("\n");

	std::vector<std::vector<IntPair> > allInversions;
	while(1){
//		printf("=============\n");
		findCycles(toShift, allInversions);
//		printf(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
//		for(int i = 1; i <= n; ++i){
//			printf("%d ", toShift[i]);
//		}
//		printf("\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");

		if (allInversions.back().size() == 0) break;
	}
	printf("%d\n", (int)allInversions.size() - 1);
	for(int i = 0; i < (int)allInversions.size() - 1; ++i){
		printf("%d\n", (int)allInversions[i].size() * 2);
		for(int j = 0; j < (int)allInversions[i].size(); ++j) printf("%d ", allInversions[i][j].first);
		for(int j = (int)allInversions[i].size() - 1; j >= 0; --j) printf("%d ", allInversions[i][j].second);
		printf("\n");
	}

	return 0;
}