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
#include <stdio.h>
#define Max 3000
int positions[Max+1];
int scaled[Max+1];
int reversed[Max+1];
bool visited[Max+1];
int n;
int outputCount[Max+1];
int output[Max+1][Max+1];
int lineIdx = 0;
int swapIdx = 0;

void push(int idx1, int idx2){
	output[lineIdx][swapIdx] = idx1;
	swapIdx++;
	output[lineIdx][swapIdx] = idx2;
	swapIdx++;
	visited[idx1] = true;
	visited[idx2] = true;
	//sort
	int temp = scaled[idx1];
	scaled[idx1] = scaled[idx2];
	scaled[idx2] = temp;
}

void swap() {	
	while(1) {
		bool sorted = true;
		for(int i=1; i<=n; i++)
			if(i != scaled[i]) 
				sorted = false;
		if(sorted)
			break;

		lineIdx++;
		
		//reset
		swapIdx = 0;
		for(int i=1; i<=n; i++)
			visited[i] = false;
		for(int i=1; i<=n; i++)
			reversed[scaled[i]] = i;

		//pick
		for(int i=1; i<=n; i++) {
			int idx1 = i;
			int idx2 = scaled[idx1];
			if(idx1 == idx2)
				continue;
			
			if(idx1 == scaled[idx2]) {//full swap
				if(visited[idx1] == false && visited[idx2] == false)
					push(idx1, idx2);
			}
			else {
				//try prepare idx1
				int idx3 = scaled[idx2];
				if(visited[idx1] == false && visited[idx3] == false) {
					push(idx1, idx3);
					visited[idx2] = true;
				}
				else {
					//try prepare idx2
					idx3 = reversed[idx1];
					if(visited[idx2] == false && visited[idx3] == false) {
						push(idx2, idx3);
						visited[idx1] = true;
					}
					else {
						//swap directly
						if(visited[idx1] == false && visited[idx2] == false)
							push(idx1, idx2);
					}
				}
			}
		}		
		outputCount[lineIdx] = swapIdx;
	}
}

int main() {
	scanf("%d", &n);
	for(int i=1; i <= n; i++) {
		int a; scanf("%d ", &a);
		positions[a] = i;		
	}
	//scale
	for(int i=1, sIdx=1; i<=Max; i++) {
		int pos = positions[i];
		if(pos > 0) {
			scaled[pos] = sIdx;
			sIdx++;
		}
	}
	swap();
	//print
	printf("%d\n", lineIdx);
	for(int l=1; l<=lineIdx; l++) {
		int count = outputCount[l];
		printf("%d\n", count);
		for(int s=0; s<count; s+=2) {
			printf("%d ", output[l][s]);
		}
		for(int s=count-1; s>=0; s-=2) {
			printf("%d ", output[l][s]);
		}
		printf("\n");
	}
	return 0;
}