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
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>

using namespace std;

unsigned min(unsigned a, unsigned b) {
    return a < b ? a : b;
}

unsigned max(unsigned a, unsigned b) {
    return a > b ? a : b;
}

int main() {
    ios_base::sync_with_stdio(false);

    unsigned n;
    cin >> n;

    unsigned h;
    vector<pair<unsigned, unsigned >> hs;

    for (auto i = 1; i <= n; i++) {
        cin >> h;
        hs.emplace_back(h, i);
    }

    sort(hs.begin(), hs.end());

    map<unsigned, unsigned> pos;
    map<unsigned, unsigned> rev_pos;

    for (unsigned i = 0; i < hs.size(); i++) {
        pos.insert(make_pair(hs[i].second, i + 1));
        rev_pos.insert(make_pair(i + 1, hs[i].second));
    }

    set<pair<unsigned, unsigned >> swaps;
    set<pair<unsigned, unsigned >> pre_swaps;

    for (int i = 1; i <= n; i++) {
        if (pos[i] == i) {
            // do nothing
        } else if (pos[pos[i]] == i) {
            // plan swap pos[i] - i
//            cout << "pos[" << i << "]: " << pos[i] << endl;
            swaps.insert(make_pair(min(i, pos[i]), max(i, pos[i])));
        } else {
//            cout << "pos[" << i << "]: " << pos[i] << endl;
            unsigned to_fix = i;
            while (to_fix != pos[to_fix] && rev_pos[to_fix] != i) {
//                cout << "Adding swap: " << min(to_fix, pos[to_fix]) << " " << max(to_fix, pos[to_fix]) << endl;

                swaps.insert(make_pair(min(to_fix, pos[to_fix]), max(to_fix, pos[to_fix])));

                if (pos[pos[to_fix]] != to_fix) {
//                    cout << "Adding pre-swap: " << min(pos[to_fix], rev_pos[to_fix]) << " "
//                         << max(pos[to_fix], rev_pos[to_fix]) << endl;
                    pre_swaps.insert(make_pair(min(pos[to_fix], rev_pos[to_fix]), max(pos[to_fix], rev_pos[to_fix])));

                    unsigned t = pos[pos[to_fix]];
                    pos[pos[to_fix]] = pos[rev_pos[to_fix]];
                    pos[rev_pos[to_fix]] = t;

//                    cout << "Setting to_fix to " << rev_pos[to_fix] << endl;
                    to_fix = rev_pos[to_fix];
                } else {
                    break;
                }
            }
        }
    }

    if (swaps.empty()) {
        cout << 0 << endl;
    } else {
        cout << (!pre_swaps.empty() ? 2 : 1) << endl;
        if (!pre_swaps.empty()) {
            cout << pre_swaps.size() * 2 << endl;
            for (auto it = pre_swaps.begin(); it != pre_swaps.end(); it++) {
                cout << (*it).first << " ";
            }
            for (auto it = pre_swaps.rbegin(); it != pre_swaps.rend(); it++) {
                cout << (*it).second << " ";
            }
            cout << endl;
        }
        if (!swaps.empty()) {
            cout << swaps.size() * 2 << endl;
            for (auto it = swaps.begin(); it != swaps.end(); it++) {
                cout << (*it).first << " ";
            }
            for (auto it = swaps.rbegin(); it != swaps.rend(); it++) {
                cout << (*it).second << " ";
            }
            cout << endl;
        }
    }

    return 0;
}