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
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second

int h[3007];
int wypisywane[3007];
vector< pair<int, int> > posortowani;
bool vis[3007];
int nr_spojnej=0;
vector<int> spojna[3007];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, j;
	cin >> n;
	posortowani.push_back({0, -1});
	for(int i=1; i<=n; ++i){
		cin >> h[i];
		posortowani.push_back({h[i], i});
	}
	bool czy_rosnacy=true;
	for(int i=2; i<=n; ++i){
        if(h[i]<h[i-1]) czy_rosnacy = false;
	}
	if(czy_rosnacy){
        cout << 0; return 0;
	}
	sort(posortowani.begin(), posortowani.end());

	/*for(int i=1; i<=n; ++i){
		cout << i << ' ' << h[i] << ' ' << posortowani[i].fi << ' ' << posortowani[i].se << endl;
	}*/
	for(int i=1; i<=n; ++i){
		//cout << i << 'j';// << h[i] << ' ' << posortowani[i].fi << ' ' << posortowani[i].se << endl;
		if(vis[i]==0){
			j = i;
			++nr_spojnej;/*
			spojna[nr_spojnej].push_back(j);
			vis[j] = 1;
			j=posortowani[j].se;*/
			while(vis[j]==0){
				//cout << j << ' ';
				vis[j] = 1;
				spojna[nr_spojnej].push_back(j);
				j=posortowani[j].se;

			}
		}
		//cout << endl;
	}
	int wynik = spojna[1].size();
	for(int i=2; i<=nr_spojnej; ++i)
		if(spojna[i].size() > wynik) wynik = spojna[i].size();
	/*for(int i=0; i<=nr_spojnej; ++i){
		for(int j=0; j<spojna[i].size(); ++j) cout << spojna[i][j] << ' ';
		cout << endl;
	}*/
	wynik = (wynik+1)/2;
	cout << wynik << '\n';// cout << 'm';
	int a, b;
	vector<int> v1, v2;
	for(int i=0; i<wynik; ++i){
		//cout << n << '\n';
		v1.clear(); v2.clear();
		for(int j=1; j<=nr_spojnej; ++j){
			if(spojna[j].size()<2) continue;
			//cout << 'k' << j << spojna[j].size() << '\t';
			for(int k=0; k<spojna[j].size()-1; k+=2){
				a = spojna[j][k]; b = spojna[j][k+1];
				//cout << a<<' '<<b<<'m';
				v1.push_back(a);
				v2.push_back(b);
				swap( h[ a ], h[ b ]);
				//cout << h[a]<<' '<<posortowani[a].fi<<'m';
				//cout << endl;

			}
			for(int k=0; k<spojna[j].size(); ++k){
				if(h[ spojna[j][k] ] == posortowani[ spojna[j][k] ].fi){
					auto it = spojna[j].begin()+k;
					spojna[j].erase(it);
				}
			}

		}
        cout << v1.size()*2 << '\n';
        for(int m=0; m<v1.size(); ++m) cout << v1[m] << ' ';
        for(int m=v2.size()-1; m>=0; --m) cout << v2[m] << ' ';
		cout << '\n';
	}

	return 0;
}