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

using namespace std;

#define M 600
#define pb push_back
 
void sort(vector<int>&t, int (*cmp)(int,int), int l, int r){      //dom-otw
    if(r-l<=1) return;
    int m=(l+r)/2, i=0, j=0, res[r-l];
    sort(t,cmp,l,m), sort(t,cmp,m,r);
    while(i+j<r-l) res[i+j-1]= (i<m-l&&j<r-m?cmp(t[i+l],t[j+m]):i<m-l) ? t[i+++l] : t[j+++m];
    for(i=0;i<r-l;i++) t[i+l]=res[i];
}
 
vector<int> tab;
 
int cmp(int l, int r){
    return tab[l]<tab[r];
}


int main(){

    int n;
    cin>>n;
    // n=10000;
    int g=1;
    // while(g){
    tab = vector<int>(n);
    for(auto&x:tab)cin>>x;
    // srand(time(0));
    // for(int i=0;i<n;i++) tab[i]=i;
    // random_shuffle(tab.begin(), tab.end());
    // cout<<"rand: "; for(auto&x:tab) cout<<x<<" "; cout<<endl;

    vector<int> perm(n);
    for(int i=0;i<n;i++) perm[i]=i;

    sort(perm, cmp, 0, n);

    // for(auto x:perm) cout<<x<<endl;

    vector<vector<int>> cycles;

    for(int i=0;i<n;i++) if(perm[i]!=-1){
        cycles.pb(vector<int>(0));
        while(perm[i]!=-1){
            cycles.back().pb(i);
            int last=i;
            i=perm[i], perm[last]=-1;
        }
    }

    // cout<<"\ncyc:\n";
    // for(int i=0;i<cycles.size();i++){
    //     for(auto j: cycles[i]) cout<<j<<" ";
    //     cout<<endl;
    // }
    int big=0;
    for(auto x:cycles) big = max(big, (int)x.size());

    //  cout<<endl;
    
    if(big==1) return cout<<"0\n", 0;
    if(big==2){
        cout<<1<<endl;
        deque<int> Q;
        for(auto x:cycles) if(x.size()==2) Q.push_back(x[0]), Q.push_front(x[1]);
        cout<<Q.size()<<endl;
        while(Q.size()) cout<<Q.front()+1<<" ", Q.pop_front();
        cout<<endl;
        return 0;
    }
    cout<<"2\n";

    deque<int> Q;

    auto put = [&](int i, int j){
        Q.push_back(i);
        Q.push_front(j);
        int l = tab[i];
        tab[i]=tab[j];
        tab[j]=l;
        // cout<<"D"<<endl;
    };

    for(auto x:cycles) for(int i=0;x.size()-1-i>i;i++) put(x[i], x[x.size()-1-i]);
    cout<<Q.size()<<endl;
    while(Q.size()) cout<<Q.front()+1<<" ", Q.pop_front();
    cout<<endl;

    for(auto x:cycles) for(int i=0;x.size()>i+i+2;i++) {
        //  cout<<i<<" "<<(int)x.size()-2-i<<" "<<((x.size()-2-i)>i)<<endl;
        put(x[i], x[x.size()-2-i]);

    }
    // cout<<"SIRT"<<endl;
    cout<<Q.size()<<endl;
    while(Q.size()) cout<<Q.front()+1<<" ", Q.pop_front();
    cout<<endl;

    // // bool g=1;
    // for(int i=0;i<n-1;i++) g = tab[i]<tab[i+1]; 
    // cout<<g;
    // }

}