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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int>> cykle;//wierzcholki na koljnych cyklach, krawedzie wartosc->pozycja
vector<vector<pair<int, int>>> wyniki;
const int limit=3e3+3;
pair<int, int> tab[limit];//nie przeskalowane
int t[limit];//przeskalowane, od 1!
bool odw[limit];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>tab[i].first;
        tab[i].second=i;
    }
    sort(tab, tab+n);
    for(int i=0; i<n; i++){
        t[tab[i].second+1]=i+1;
    }
    for(int i=1; i<=n; i++){
        if(!odw[i]){
            int x=i;
            vector<int> wierzcholki={};
            do{
                odw[x]=1;
                wierzcholki.push_back(x);
                x=t[x];
            }
            while(x!=i);
            if(wierzcholki.size()>1){
                cykle.push_back(wierzcholki);
            }
        }
    }
    int maks=0;
    for(auto i:cykle){
        maks=max(maks, int(i.size()));
    }
    if(maks<2){
        cout<<0;
        return 0;
    }
    if(maks==2){
        cout<<1<<'\n';
        int ile=0;
        for(auto i:cykle){
            ile+=(i.size()==2);
        }
        cout<<2*ile<<'\n';
        for(auto i:cykle){
            if(i.size()==2){
                cout<<i[0]<<' ';
            }
        }
        for(int i=cykle.size()-1; i>=0; i--){
            if(cykle[i].size()==2){
                cout<<cykle[i][1]<<' ';
            }
        }
        return 0;
    }
    cout<<"2\n";
    vector<pair<int, int>> teraz, potem;//swapy na teraz, na potem
    for(auto i:cykle){
        if(i.size()%2==0){
            for(int j=0; j<int(i.size()/2)-1; j++){
                teraz.push_back({i[j], i[i.size()-2-j]});//0 z n-2
                potem.push_back({i[j], i[i.size()-1-j]});//0 z n-1
            }
            potem.push_back({i[i.size()/2-1], i[i.size()/2]});
        }
        else{
            for(int j=0; j<int(i.size()/2); j++){
                teraz.push_back({i[j], i[i.size()-2-j]});//0 z n-2
                potem.push_back({i[j], i[i.size()-1-j]});//0 z n-1
            }
        }
    }
    cout<<teraz.size()*2<<'\n';
    for(auto i:teraz){
        cout<<i.first<<' ';
    }
    for(int i=int(teraz.size())-1; i>=0; i--){
        cout<<teraz[i].second<<' ';
    }
    cout<<'\n'<<potem.size()*2<<'\n';
    for(auto i:potem){
        cout<<i.first<<' ';
    }
    for(int i=int(potem.size())-1; i>=0; i--){
        cout<<potem[i].second<<' ';
    }
}