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

#define fi first
#define se second

const int N = 3005;

pair <int, int> tab[N];

int val[N];
bool odw[N];

int kol = 0;
int maxim = 0;

int wypisz[N];

vector <int> v[N];

int n;

void dfs(int x, int r){
    odw[x] = 1;
    v[r].push_back(x);

    if(!odw[val[x]]) dfs(val[x], r);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for(int i = 1; i <= n; i++){
        int a;
        cin >> a;
        tab[i] = make_pair(a, i);
    }

    sort(tab + 1, tab + n + 1);

    for(int i = 1; i <= n; i++){
        val[tab[i].second] = i;
    }

    for(int i = 1; i <= n; i++){
        if(odw[i]) continue;

        dfs(i, i);

        if(v[i].size() == 2) maxim = max(maxim, 1);
        else if(v[i].size() > 2) maxim = max(maxim, 2);
    }

    cout << maxim << "\n";

    vector <pair <int, int> > q;

    for(int i = 1; i <= n; i++){
        //odw[i] = 0;
        if(v[i].size() <= 1) continue;
        //q.push_back(make_pair(v[i][0], v[i][1]));

        int a = v[i].size() - 1, b = 0;
        while(a > b){
            int x = v[i][a], y = v[i][b];
            q.push_back(make_pair(x, y));
            swap(val[x], val[y]);
            a--;
            b++;
        }
    }

    //cout << q.size() << "\n";

    int l = q.size() * 2;
    
    if(l > 0){
        cout << l << "\n";
        for(int i = 0; i < q.size(); i++){
            cout << q[i].fi << " ";
        }
        for(int i = q.size() - 1; i >= 0; i--){
            cout << q[i].se << " ";
        }
        cout << "\n";
    }

    q.clear();

    for(int i = 1; i <= n; i++){
        if(val[i] != i && val[i] > i){
            q.push_back(make_pair(i, val[i]));
        }
    }

    l = q.size() * 2;

    if(l > 0){
        cout << l << "\n";
        for(int i = 0; i < q.size(); i++){
            cout << q[i].fi << " ";
        }
        for(int i = q.size() - 1; i >= 0; i--){
            cout << q[i].se << " ";
        }
    }

}