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
#include <cstdio>
#include <cstdlib>
#include <cstring>

static int cmp(const void *pa, const void *pb)
{
	return *(int *) pa - *(int *) pb;
}

#define	MAX_N	3000

unsigned tab[MAX_N + 1];
unsigned tab2[MAX_N + 1];
int tmp[MAX_N + 1];
unsigned indices[MAX_N + 1];
unsigned result[MAX_N];

int main(void)
{
	unsigned n, i, r = 0;

	scanf("%u", &n);

	for (i = 1; i <= n; i++)
		scanf("%u", &tab[i]);

	memcpy(tab2 + 1, tab + 1, n * sizeof(tab[0]));
	memcpy(tmp + 1, tab + 1, n * sizeof(tab[0]));
	qsort(tmp + 1, n, sizeof(tmp[0]), cmp);
	for (i = 1; i <= n; i++)
		indices[tmp[i]] = i;

	/*
	for (i = 1; i <= n; i++)
		printf("%u: %u -> %u\n", tab[i], i, indices[tab[i]]);
	*/

	for (;;) {
		unsigned len = 0;
		memset(tmp + 1, 0, n * sizeof(tmp[0]));

		for (i = 1; i < n; i++) {
			unsigned j = indices[tab[i]];

			if (i != j && !tmp[i] && !tmp[j]) {
				//printf("%u <=> %u\n", i, j);
				tmp[i] = j;
				tmp[j] = i;
				result[len++] = i;
				result[len++] = j;
			}
		}

		if (len) {
			for (i = 0; i < len; i += 2) {
				unsigned p, q, x;

				p = result[i];
				q = result[i + 1];
				x = tab[p];
				tab[p] = tab[q];
				tab[q] = x; 
			}
		} else {
			break;
		}

		r++;
	}

	printf("%u\n", r);

	for (;;) {
		unsigned len = 0;
		memset(tmp + 1, 0, n * sizeof(tmp[0]));

		for (i = 1; i < n; i++) {
			unsigned j = indices[tab2[i]];

			if (i != j && !tmp[i] && !tmp[j]) {
				//printf("%u <=> %u\n", i, j);
				tmp[i] = j;
				tmp[j] = i;
				result[len++] = i;
				result[len++] = j;
			}
		}

		if (len) {
			printf("%u\n", len);
			for (i = 0; i < len; i += 2) {
				if (i)
					putchar(' ');
				printf("%u", result[i]);
			}
			for (i = len; i > 0; i -= 2) {
				printf(" %u", result[i - 1]);
			}
			putchar('\n');

			for (i = 0; i < len; i += 2) {
				unsigned p, q, x;

				p = result[i];
				q = result[i + 1];
				x = tab2[p];
				tab2[p] = tab2[q];
				tab2[q] = x; 
			}
		} else {
			break;
		}
	}

	return 0;
}