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

using namespace std;
int tab[3009];
map<int, int> M;
int graf[3009], odw[3009];
vector<pair<int, int>> vec;
vector<int> pierwszy, drugi, cykl;

void parzysta() {
    int pom;
    for(int i=0; i<cykl.size()/2; i++) {
        pierwszy.push_back(cykl[i]);
        pierwszy.push_back(cykl[cykl.size()-1-i]);
        pom=tab[cykl[i]];
        tab[cykl[i]]=tab[cykl[cykl.size()-1-i]];
        tab[cykl[cykl.size()-1-i]]=pom;
        //swap(tab[cykl[i]], tab[cykl[cykl.size()-1-i]]);
    }
}

void nieparzysta() {
    int pom;
    for(int i=0; i<cykl.size()/2; i++) {
        //cout << "PARUJE: " << cykl[i] << ' ' << cykl[cykl.size()-1-i] << endl;
        pierwszy.push_back(cykl[i]);
        pierwszy.push_back(cykl[cykl.size()-1-i]);
        pom=tab[cykl[i]];
        tab[cykl[i]]=tab[cykl[cykl.size()-1-i]];
        tab[cykl[cykl.size()-1-i]]=pom;
        //swap(tab[cykl[i]], tab[cykl[cykl.size()-1-i]]);
    }
    /// xd to to samo?
}

void DFS(int v) {
    cykl.push_back(v);
    int w=graf[v];
    odw[v]=1;
    while(w!=v) {
        cykl.push_back(w);
        odw[w]=1;
        w=graf[w];
    }
    //cout << v << " CYKL = " << cykl.size() << endl;
    if(cykl.size()%2==0) {
        parzysta();
    }
    else {
        nieparzysta();
    }
    cykl.clear();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, a;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> a;
        vec.push_back({a, i});
    }
    sort(vec.begin(), vec.end());
    for(int i=1; i<=vec.size(); i++) {
        tab[vec[i-1].second+1]=i;
        M[i]=vec[i-1].second+1;
    }
    bool czy=1;
    for(int i=1; i<=n; i++) {
        if(tab[i]!=i) {
            czy=0;
            break;
        }
    }
    /*for(int i=1; i<=n; i++) {
        cout << tab[i] << ' ';
    }*/
    //cout << endl;
    if(czy) {
        cout << 0;
        return 0;
    }
    for(int i=1; i<=n; i++) {
        graf[i]=tab[i];
    }
    /*for(int i=1; i<=n; i++) {
        cout << graf[i] << ' ';
    }*/
    //cout << endl;
    for(int i=1; i<=n; i++) {
        if(tab[i]==i or tab[tab[i]]==i or odw[i]) {
            continue;
        }
        DFS(i);
    }
    for(int i=1; i<=n; i++) {
        if(tab[i]!=i) {
            drugi.push_back(i);
            drugi.push_back(tab[i]);
            swap(tab[i], tab[tab[i]]);
        }
    }
    int wyn=0;
    if(pierwszy.size()!=0) {
        wyn++;
    }
    if(drugi.size()!=0) {
        wyn++;
    }
    cout << wyn << endl;
    if(pierwszy.size()!=0) {
        cout << pierwszy.size() << endl;
        for(int i=0; i<pierwszy.size(); i+=2) {
            cout << pierwszy[i] << ' ';
        }
        for(int i=pierwszy.size()-1; i>=1; i-=2) {
            cout << pierwszy[i] << ' ';
        }
        cout << endl;
    }
    if(drugi.size()!=0) {
        cout << drugi.size() << endl;
        for(int i=0; i<drugi.size(); i+=2) {
            cout << drugi[i] << ' ';
        }
        for(int i=drugi.size()-1; i>=1; i-=2) {
            cout << drugi[i] << ' ';
        }
    }
    //cout << endl;
    //for(int i=1; i<=n; i++) {
    //    cout << tab[i] << ' ';
    //}
    //cout << endl;
    //cout << endl << wyn << endl;
    return 0;
}