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
#include <vector>
#include <iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> w(n);
	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}

	vector<int> rank(3001);

	for (int i = 0; i < n; i++) {
		rank[w[i]] = 1;
	}

	int currentRank = 1;
	for (int i = 0; i < rank.size(); i++) {
		if (rank[i] == 1) {
			rank[i] = currentRank;
			currentRank++;
		}
	}

	//for (int i = 0; i < rank.size(); i++) {
	//		cout << i << ": " << rank[i] << " " << endl;
	//}

	for (int i = 0; i < n; i++) {
		w[i] = rank[w[i]];
	}

	//for (int i = 0; i < n; i++) {
	//	cout << w[i] << " ";
	//}


	// create lookup
	vector<int> lookup(n + 1);
	for (int i = 0; i < n; i++) {
		lookup[w[i]] = i;
	}

	vector<vector<int>> cycles;
	vector<vector<int>> arrangements;

	do {
		// cycles
		vector<bool> visited(n);
		cycles.clear();

		for (int i = 0; i < n; i++) {
			if (visited[i] == true) {
				continue;
			}
			visited[i] = true;
			vector<int> cycle;
			cycle.push_back(w[i]);
			int currentIndex = w[i] - 1;
			while (currentIndex != i) {
				visited[currentIndex] = true;
				cycle.push_back(w[currentIndex]);
				currentIndex = w[currentIndex] - 1;
			}
			// cycle done, add
			if (cycle.size() > 1) {
				cycles.push_back(cycle);
			}
			
		}

		//cout << endl;
		//for (int i = 0; i < cycles.size(); i++) {
		//	for (int j = 0; j < cycles[i].size(); j++) {
		//		cout << cycles[i][j] << " ";
		//	}
		//	cout << endl;
		//}

		// remove elements from each cycle
		vector<vector<int>> indexPairsToSwap;
		for (int i = 0; i < cycles.size(); i++) {
			vector<int> indexPairToSwap;

			for (int j = 0; j < cycles[i].size() - 1; j += 2) {
				indexPairToSwap.push_back(cycles[i][j]);
				int homeIndex = cycles[i][j] - 1;
				indexPairToSwap.push_back(w[homeIndex]);
				indexPairsToSwap.push_back(indexPairToSwap);
			}
		}

		vector<int> arrangement(2 * indexPairsToSwap.size());
		for (int i = 0; i < indexPairsToSwap.size(); i++) {
			arrangement[i] = indexPairsToSwap[i][0];
			arrangement[arrangement.size() - 1 - i] = indexPairsToSwap[i][1];
		}

		arrangements.push_back(arrangement);

		// output arrangement, set up new order

		//cout << endl;

		for (int i = 0; i < indexPairsToSwap.size(); i++) {
			int tmp = w[indexPairsToSwap[i][0] - 1];
			w[indexPairsToSwap[i][0] - 1] = w[indexPairsToSwap[i][1] - 1];
			w[indexPairsToSwap[i][1] - 1] = tmp;
		}

		//cout << endl;
	} while (cycles.size() > 0);

	cout << arrangements.size() - 1 << endl;

	for (int i = 1; i < arrangements.size(); i++) {
		
		for (int j = 0; j < arrangements[i].size(); j++) {
			cout << arrangements[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}