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

pair<int, int> nums[3007];
int stage[3007];
vector<pair<int,int>> ch[3];
vector<int> cycle;
bitset<3007> seen;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, a;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a;
		nums[i] = {a, i};
	}
	sort(nums + 1, nums + n + 1);
	for (int i = 1; i <= n; i++) {
		stage[nums[i].second] = i;
	}
	
    bool done;
    int res, v;
    for(res=0; res<3; res++){
        done = 1;
        for (int i = 1; i <= n; i++){
            if(i==stage[i]) seen[i] = 1;
            else{
                seen[i] = 0;
                done = false;
            }
        }
        if(done) break;
        for(int i=1; i<=n; i++){
            if(!seen[i]){
                seen[i]=1;
                v = stage[i];
                cycle.clear();
                cycle.push_back(i);
                while(v!=i){
                    cycle.push_back(v);
                    seen[v] = true;
                    v = stage[v];
                }
                if(cycle.size() == 2){
                    ch[res].push_back({cycle[0], cycle[1]});
                    swap(stage[cycle[0]], stage[cycle[1]]);
                    continue;
                }
                for(int j=1; j<=(cycle.size()-1)/2; j++){
                    ch[res].push_back({cycle[j], cycle[cycle.size()-j]});
                    swap(stage[cycle[j]], stage[cycle[cycle.size()-j]]);
                }
            }
        }
    }
    cout << res << '\n';
    for(int i=0; i<res; i++){
        cout << ch[i].size()*2 << '\n';
        for(int j=0; j<ch[i].size(); j++) cout << ch[i][j].first << ' ';
        for(int j=ch[i].size()-1; j>=0; j--) cout << ch[i][j].second << ' ';
        cout << '\n';
    }
}