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
// Wojciech Widomski
#include <iostream>
#include <vector>
using namespace std;

#define MAX_N 3000

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

    int n;
    cin >> n;

    vector<int> wysokosci(n);

    for (int i = 0; i < n; i++) {
        cin >> wysokosci[i];
    }

    // Należy ponumerować wysokości on najmniejszej do największej
    // Jest ich tylko 3000, więc O(n^2)
    vector<int> numery(n);

    int nast_numer = 0;
    for (int i = 1; i <= MAX_N; i++) {
        for (int j = 0; j < n; j++) {
            if (wysokosci[j] == i) {
                numery[j] = nast_numer;
                nast_numer++;
            }
        }
    }

    vector<int> pozycje_numerow(n);

    for (int i = 0; i < n; i++) {
        pozycje_numerow[numery[i]] = i;
    }


    // Każdy element wektora jest jedną rundą wywołań.
    // Jest on parą, której pierwszy element to wektor
    // z numerami na początku, a drugi na końcu.
    vector<pair<vector<int>, vector<int>>> zamiany;

    bool uporzadkowane = false;
    while (!uporzadkowane) {
        pair<vector<int>, vector<int>> runda;
        bool* zmienione_w_rundzie = new bool[n]();
        for (int i = 0; i < n; i++) {
            if (numery[i] != i && !zmienione_w_rundzie[i] && !zmienione_w_rundzie[pozycje_numerow[i]]) {
                runda.first.push_back(i);
                runda.second.push_back(pozycje_numerow[i]);
                zmienione_w_rundzie[i] = true;
                zmienione_w_rundzie[pozycje_numerow[i]] = true;
                
                int tmp = numery[i];
                numery[i] = i;
                numery[pozycje_numerow[i]] = tmp;

                pozycje_numerow[tmp] = pozycje_numerow[i];
                pozycje_numerow[i] = i;
            } else if (numery[i] != i && !zmienione_w_rundzie[i] && !zmienione_w_rundzie[numery[i]]) {
                runda.first.push_back(i);
                runda.second.push_back(numery[i]);
                zmienione_w_rundzie[i] = true;
                zmienione_w_rundzie[numery[i]] = true;
                int tmp = numery[i];
                numery[i] = numery[tmp];
                numery[tmp] = tmp;

                pozycje_numerow[tmp] = tmp;
                pozycje_numerow[numery[i]] = i;
            }
        }
        if (runda.first.empty()) {
            uporzadkowane = true;
        } else {
            zamiany.push_back(runda);
        }
    }
    
    cout << zamiany.size() << "\n";

    for (int i = 0; i < zamiany.size(); i++) {
        cout << 2*zamiany[i].first.size() << "\n";
        for (int j = 0; j < zamiany[i].first.size(); j++) {
            cout << zamiany[i].first[j]+1 << " ";
            // cout << zamiany[i].first[j] << " ";
        }
        for (int j = zamiany[i].second.size()-1; j >= 0; j--) {
            cout << zamiany[i].second[j]+1 << " ";
            // cout << zamiany[i].second[j] << " ";
        }
        cout << "\n";
    }

    return 0;
}