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
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <utility>

using namespace std;

void createCycle(
        int index,
        const vector<int> &items,
        const vector<int> &sorted,
        vector<bool> &visited,
        list<list<int> > &cycles) {
    visited[index] = true;
    if (items[index] == sorted[index]) return;
    cycles.emplace_back();
    cycles.back().push_back(index);

    while (true) {
        int destination = distance(sorted.begin(), lower_bound(sorted.begin(), sorted.end(), items[index]));
        if (cycles.back().front() == destination) break;
        cycles.back().push_back(destination);
        index = destination;
        visited[destination] = true;
    }
}

int getRoundsFromCycleSize(int cycleSize) {
    int result = 0;
    while (cycleSize > 1) {
        cycleSize = cycleSize / 2 + (cycleSize % 2 == 1);
        result++;
    }
    return result;
}


int calculateRounds(const list<list<int> > &cycles) {
    int cycleSize = 0;
    for (auto &cycle: cycles) {
        cycleSize = max(cycleSize, (int) cycle.size());
    }

    return getRoundsFromCycleSize(cycleSize);
}

int executeRound(list<int> &cycle, vector<pair<int, int> > &pairsContainer) {
    int pairs = 0;
    auto it = cycle.begin();
    while (it != cycle.end()) {
        auto nextIt = next(it, 1);
        if (nextIt == cycle.end()) {
            break;
        }
        pairsContainer.emplace_back(*it, *nextIt);
        pairs++;
        it = cycle.erase(nextIt);
        advance(it, 1);
    }
    return pairs;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> items, sorted;
    items.reserve(n);

    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        items.push_back(v);
    }

    sorted.resize(n);
    copy(items.begin(), items.end(), sorted.begin());
    sort(sorted.begin(), sorted.end());

    vector<bool> visited(n, false);
    list<list<int> > cycles;

    for (int i = 0; i < n; i++) {
        if (visited[i]) {
            continue;
        }
        createCycle(i, items, sorted, visited, cycles);
    }

    int rounds = calculateRounds(cycles);
    cout << rounds << endl;

    while (!cycles.empty()) {
        vector<pair<int, int> > pairsToSwap;
        for (auto it = cycles.begin(); it != cycles.end();) {
            int count = executeRound(*it, pairsToSwap);
            if (count == 0) it = cycles.erase(it);
            else ++it;
        }

        if (pairsToSwap.empty()) break;
        cout << pairsToSwap.size() * 2 << endl;

        for (auto &pair: pairsToSwap) {
            cout << pair.first + 1 << " ";
        }
        for (auto rit = pairsToSwap.rbegin(); rit != pairsToSwap.rend(); ++rit) {
            cout << rit->second + 1 << " ";
        }
        cout << endl;
    }

    return 0;
}