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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <algorithm>
int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int> > wz;
    std::vector<std::vector<int> > cykle;
    std::vector<bool> pass;
    pass.resize(n, false);
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        wz.emplace_back(a, i);
    }
    bool nottrivial=false;
    sort(wz.begin(), wz.end());
    std::vector<int> inversion;
    inversion.resize(n);
    for(int i=0;i<n;i++)
        inversion[wz[i].second]=i;
    for (int i = 0; i < n; i++) {
        //std::cout<<"i"<<i<<std::endl;
        if (inversion[i]!= i && pass[i] == false) {
            cykle.emplace_back(std::vector<int>());
            pass[i] = true;
            int pom = inversion[i];
            cykle.back().emplace_back(pom);
            while (pom != i) {
                pass[pom] = true;
                pom = inversion[pom];
                cykle.back().emplace_back(pom);
            }
            if(cykle.back().size()>2)
                nottrivial=true;

        }
    }
    if(cykle.size()==0) {
        std::cout << 0 <<"\n";
        return 0;
    }
    std::vector<int> result;
    if(nottrivial== false) {
        std::cout << 1 <<"\n";
        for(int i=0;i<cykle.size();i++)
            result.emplace_back(cykle[i][0]);;
        for(int i=cykle.size()-1;i>=0;i--)
            result.emplace_back(cykle[i][1]);
        std::cout<<result.size()<<"\n";
        for(int i=0;i<result.size();i++)
            std::cout<<result[i]+1<<" ";
        return 0;
    }
    std::cout<<2<<std::endl;
    for(int i=0;i<cykle.size();i++)
        for(int j=0;j<=(int(cykle[i].size())-1)/2-1;j++) {
            result.emplace_back(cykle[i][(j+cykle[i].size()-1)%cykle[i].size()]);
            //std::cout<<cykle[i].size()<<"hit"<<j<<" "<<(j+cykle[i].size()-1)%cykle[i].size()<<std::endl;
        }
    for(int i=cykle.size()-1;i>=0;i--)
        //for(int j=cykle[i].size()-2;j>=(cykle[i].size())/2;j--){
        for(int j=(cykle[i].size())/2;j<=cykle[i].size()-2;j++){
            result.emplace_back(cykle[i][(j+cykle[i].size()-1)%cykle[i].size()]);

            //std::cout<<"ban"<<j<<" "<<(j+cykle[i].size()-1)%cykle[i].size()<<std::endl;
        }
    std::cout<<result.size()<<std::endl;
    for(int i=0;i<result.size();i++)
        std::cout<<result[i]+1<<" ";



    sort(wz.begin(), wz.end(),[&](const std::pair<int,int> &a,const std::pair<int,int> &b){return a.second<b.second;});
    for(int i=0;i<result.size()/2;i++){
        swap(wz[result[i]],wz[result[result.size()-1-i]]);
    }
    std::cout<<"\n";
    for(int i=0;i<n;i++){
        wz[i].second=i;
        //std::cout<<wz[i].first<<std::endl;
    }


    /*result.clear();
    for(int i=0;i<cykle.size();i++){
        for(int j=0;j<=cykle[i].size()/2-1;j++)
            result.emplace_back(cykle[i][(j+cykle[i].size()-1)%cykle[i].size()]);
    }
    for(int i=cykle.size()-1;i>=0;i--) {
        for (int j=cykle.size()-1;j>=(cykle[i].size()+1)/2;j--)
            result.emplace_back(cykle[i][(j+cykle[i].size()-1)%cykle[i].size()]);
    }*/
    /*std::cout<<result.size()<<"\n";
    for(int i=0;i<result.size();i++)
        std::cout<<result[i]<<" ";
    std::cout<<"\n";*/
   /* std::cout<<"deb"<<"\n";
    for (auto x: cykle) {
        for (auto y: x)
            std::cout<<y<<" ";
        std::cout<<std::endl;
    }*/
    nottrivial=false;
    cykle.clear();
    sort(wz.begin(), wz.end());
    result.clear();
    for(int i=0;i<n;i++) {
        inversion[wz[i].second] = i;
        pass[i]=false;
    }
    for (int i = 0; i < n; i++) {
        if (inversion[i]!= i && pass[i] == false) {
            cykle.emplace_back(std::vector<int>());
            pass[i] = true;
            int pom = inversion[i];
            cykle.back().emplace_back(pom);
            while (pom != i) {
                pass[pom] = true;
                pom = inversion[pom];
                cykle.back().emplace_back(pom);
            }
            if(cykle.back().size()>2)
                nottrivial=true;

        }
    }
    if(nottrivial)
        std::cout<<"error"<<std::endl;
    for(int i=0;i<cykle.size();i++)
        result.emplace_back(cykle[i][0]);;
    for(int i=cykle.size()-1;i>=0;i--)
        result.emplace_back(cykle[i][1]);
    std::cout<<result.size()<<"\n";
    for(int i=0;i<result.size();i++)
        std::cout<<result[i]+1<<" ";
    /*std::cout<<"deb"<<"\n";
    for (auto x: cykle) {
        for (auto y: x)
            std::cout<<y<<" ";
        std::cout<<std::endl;
    }*/
    return 0;
}