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
// Wiktor Kotala
// O(n + sort(n))
#include <bits/stdc++.h>
#define f first
#define s second
#define add push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
const int N = 3003;
pint H[N];
int wsk[N];
vector< vector<int> > cykl;
bool rozpatrzony[N];
vector<pint> zamiany[2];

void wypisz_rundy(int i){
    if(zamiany[i].size()){
        cout << 2*zamiany[i].size() << '\n';
        for(const pint& p : zamiany[i])
            cout << p.f << ' ';

        reverse(zamiany[i].begin(), zamiany[i].end());
        for(const pint& p : zamiany[i])
            cout << p.s << ' ';

        cout << '\n';
    }
    return;
}

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

    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> H[i].f;
        H[i].s = i;
    }
    sort(H+1, H+n+1);

    for(int i=1; i<=n; i++){
        wsk[H[i].s] = i;
    }

    for(int i=1; i<=n; i++){
        if(!rozpatrzony[i]){
            cykl.add({});
            int j = i;
            cykl.back().add(j);
            rozpatrzony[j] = 1;

            while(wsk[j] != cykl.back().front()){
                j = wsk[j];
                cykl.back().add(j);
                rozpatrzony[j] = 1;
            }
        }
    }

    for(const vector<int>& C : cykl){
        int p=0, k=C.size()-1;
        while(p < k){
            zamiany[0].add({C[p], C[k]});
            p++;
            k--;
        }

        p=1; k = C.size()-1;
        while(p < k){
            zamiany[1].add({C[p], C[k]});
            p++;
            k--;
        }
    }

    if(zamiany[1].size()){
        cout << 2 << '\n';
    }
    else if(zamiany[0].size()){
        cout << 1 << '\n';
    }
    else{
        cout << 0 << '\n';
    }

    wypisz_rundy(0);
    wypisz_rundy(1);

	return 0;
}