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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>

using namespace std;

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    cin >> n;
    int *tab_dl = new int [n];
    int *tab_kol = new int [n];
    for(int i = 0; i < n; i++){
        cin >> tab_dl[i];
    }
    for(int i = 0; i < n; i++){
        int max_w = 0;
        int max_id;
        for(int j = 0; j < n; j++){
            if(tab_dl[j] > max_w){
                max_w = tab_dl[j];
                max_id = j;
            }
        }
        tab_kol[n-1-i] = max_id;
        tab_dl[max_id] = 0; 
    }
    // for(int i = 0; i < n; i++){
    //     cout << tab_kol[i] << " ";
    // }
    
    
    
    // 2 etap - podział na ciągi
    int **ciagi = new int*[n];
    int ile_ciagow = 0;
    int *ciagi_dl = new int[n];
    int *ciagi_tym = new int [n];
    int max_dl = 0;

     
    for(int i = 0;i < n; i++){
        if(tab_dl[i] != -1 and i != tab_kol[i]){
            int *ciagi_tym = new int [n];
            int j = tab_kol[i];
            int ciagi_dl_tym = 1;
            ciagi_tym[ciagi_dl_tym-1] = tab_kol[i];
            while(tab_kol[i] != tab_kol[j]){
                tab_dl[j] = -1;
                ciagi_tym[ciagi_dl_tym] = tab_kol[j];
                int l = j;
                j = tab_kol[l];
                ciagi_dl_tym++;
            }
            ciagi_dl[ile_ciagow] = ciagi_dl_tym;
            ciagi[ile_ciagow] = ciagi_tym;
            ile_ciagow++;
            if(max_dl < ciagi_dl_tym){
                max_dl = ciagi_dl_tym;
            }
        }
    }
    // etap 3 wypisywanie operacji;
    int powt = 0;
    // while(max_dl != 1){
    while (max_dl > 1) {
        if(max_dl%2 == 1){
            max_dl++;
        }
        max_dl /= 2;
        powt++;
    }
    cout << powt << "\n";

    int *ciag_poczatek = new int [n];
    int *ciag_koniec = new int [n];
    int poczetek_id = 0;
    int koniec_id = 0;

    for(int i = 0; i < powt; i++){
        poczetek_id = 0;
        koniec_id = 0;
        for(int j = 0; j < ile_ciagow; j++){
            if(ciagi_dl[j] != 1){
                int ile_par = (ciagi_dl[j])/2;
                for(int l = 0; l < ile_par; l++){
                    ciag_poczatek[poczetek_id] = ciagi[j][2*l];
                    ciag_koniec[koniec_id] = ciagi[j][(2*l)+1];
                    poczetek_id++;
                    koniec_id++;
                    ciagi[j][2*l] = 0;
                    ciagi[j][l] = ciagi[j][(2*l)+1];
                }
                if(ciagi_dl[j]%2 == 1){
                    ciagi[j][ile_par] = ciagi[j][ciagi_dl[j]-1];
                    ciagi_dl[j] = ile_par + 1;
                }
                else{
                    ciagi_dl[j] = ile_par;
                }

            }
        }
        cout << poczetek_id * 2 << "\n";
        for(int j = 0; j < poczetek_id; j++){
            cout << ciag_poczatek[j] + 1;
            if (j != poczetek_id -1) {
                cout << " ";
            }
        }
        for(int j = 0; j < koniec_id; j++){
            cout << " " << ciag_koniec[koniec_id - 1 - j] + 1;
        }
        cout << "\n";
    }




    for(int i = 0; i < ile_ciagow; i++){
        delete [] ciagi[i];
    }


    delete [] ciag_poczatek;
    delete [] ciag_koniec;
    delete [] ciagi_dl;
    delete [] ciagi_tym;
    delete [] ciagi;
    delete [] tab_dl;
    delete [] tab_kol;
    return 0;
}