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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;

bool compare_pair(const pair<short int, short int>& pair1,
    const pair<short int, short int>& pair2)
{
    if ((pair2.first > pair1.first) ||
        ((pair2.first == pair1.first)))
    {
        return 1;
    }
    return 0;
}

short int znajdz(pair<short int, short int>* szereg, const short int &zmiana) {
    int i = 0;
    while (szereg[i].first != zmiana) i++;
    return i;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    short int n;
    cin >> n;
    pair<short int,short int>* szereg = new pair<short int, short int>[n];
    pair<short int, short int>* wzor = new pair<short int, short int>[n];
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        szereg[i]=make_pair(x,i);
        wzor[i]=make_pair(x,i);
    }
    sort(wzor, wzor+n, &compare_pair);
    bool* praw = new bool[n]{0};
    int zmiany=0;
    vector<short int> kol;
    for (int i = 0; i < n; i++) {
        if (wzor[i].second == i) {
            praw[i] = true; zmiany++;
        }
        else {
            kol.push_back(wzor[i].first);
        }
        szereg[wzor[i].second].second = i;
    }
    zmiany = n - zmiany;
    string full="";
    int fullZmiany = 0;
    while (zmiany > 0) {
        bool* tmpZmiany=new bool[n]{0};
        vector<short int> kolejka;
        for (int j = 0; j < kol.size(); j++) {
            int i = znajdz(szereg, kol[j]);
            if (szereg[i].second != i && tmpZmiany[szereg[i].second]!=1 && tmpZmiany[i]!=1) {
                kolejka.push_back(i + 1);
                kolejka.push_back(szereg[i].second+1);
                tmpZmiany[i] = 1;
                tmpZmiany[szereg[i].second] = 1;
                praw[i] = 1;
                zmiany--;
                if (szereg[szereg[i].second].second == i) {
                    zmiany--; praw[szereg[i].second] = 1;
                }
                pair<short int, short int>tmp1 = szereg[i], tmp2= szereg[szereg[i].second];
                szereg[tmp1.second] = tmp1;
                szereg[i] = tmp2;
        //cout << "D";
                kol.erase(kol.begin() + j);
                j--;
            }
        }
        full += to_string(kolejka.size())+"\n";
        int i;
        for (i = 0; i < kolejka.size(); i += 2) full += to_string(kolejka[i]) + " ";
        for (i--; i > 0; i -= 2) full += to_string(kolejka[i]) + " ";
        full += "\n";
        fullZmiany++;
        delete tmpZmiany;
    }

        //for (int i = 0; i < n; i++) cout << wzor[i].first << " ";
        //cout << endl;
    cout << fullZmiany << "\n" << full;

    delete szereg, wzor, praw;
    return 0;
}