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

using namespace std;

const int N = 3005;
bitset<N> used;
int tab[N],Prev[N];

bool sorted(int n){
    for(int i=0; i<n; ++i){
        if(i!=tab[i]){
            return false;
        }
    }
    return true;
}

bool cmp(const pair<int,int> &a, const pair<int,int> &b){
    return a.first < b.first;
}

int main(){
    ios_base::sync_with_stdio(0);
    int n,res=1;
    vector<deque<int>> moves(2);
    vector<pair<int,int>> tab2;

    cin >> n;
    for(int i=0; i<n; ++i){
        cin >> tab[i];
        tab2.push_back({tab[i], i});
    }
    sort(tab2.begin(),tab2.end(),cmp);
    for(int i=0; i<n; ++i){
        tab2[i].first = i;
    }
    for(int i=0; i<n; ++i){
        tab[tab2[i].second] = tab2[i].first;
    }
    for(int i=0; i<n; ++i){
        Prev[tab[i]] = i;
//        cout << tab[i] << ' ';
    }
//    cout << endl;
//    for(int i=0; i<n; ++i){
//        cout << Prev[i] << ' ';
//    }

//    cout << endl << endl;
    if(sorted(n)){
        cout << 0;
        return 0;
    }

    for(int i=0; i<n; ++i){
        int elem = i;
//        if(used[Prev[elem]] || used[tab[elem]]) continue;
//        if(elem == tab[elem]) continue;
//        if(Prev[elem] == tab[elem]) continue;
        int prevv = Prev[elem];
        int nextt = tab[elem];
        while(true){
            if(used[prevv] || used[nextt]) break;
            if(elem == nextt) break;
            if(prevv == nextt) break;
//            cout << "I: "<< i << " elem:" << elem << " next:" << nextt << " prev:" << prevv << endl;
            res = 2;
            moves[0].push_front(nextt);
            moves[0].push_back(prevv);
            used[nextt] = 1;
            used[prevv] = 1;
            swap(tab[nextt], tab[prevv]);
            elem = prevv;

            prevv = Prev[elem];
            nextt = tab[elem];
        }
    }
    for(int i=0; i<n; ++i){
        if(tab[tab[i]] == i && tab[i]<i){
            moves[1].push_front(i);
            moves[1].push_back(tab[i]);
        }
    }
    cout << res << '\n';
    if(res == 2){
        cout << moves[0].size() << '\n';
        while(!moves[0].empty()){
            cout << moves[0].front()+1 << " ";
            moves[0].pop_front();
        }
        cout << '\n';
    }
    cout << moves[1].size() << '\n';
    while(!moves[1].empty()){
        cout << moves[1].front()+1 << " ";
        moves[1].pop_front();
    }
    return 0;
}