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
#include <cstdio>
#include <cassert>
#include <algorithm>

const int MAXN = 3000;

int a[MAXN+5];
int sorted[MAXN+5];
int cel[MAXN+5];
int mapa[MAXN+5];
bool wolny[MAXN+5];
int zamiany[MAXN+5][2];
int ppol;

int cykl[MAXN+5];
int ncykl;

#define NDEBUG

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", a+i);
        sorted[i] = a[i];
        assert(a[i] <= 3000 && a[i] >= 1);
    }
    std::sort(sorted, sorted+n);
    for (int i = 0; i < n; ++i) {
        mapa[sorted[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        cel[i] = mapa[a[i]];
    }
    for (int i = 0; i < n; ++i) {
        wolny[i] = true;
    }
    int kolejny, dlmax = 0;
    for (int i = 0; i < n; ++i) {
        ncykl = 0;
        if (wolny[i]) {
            kolejny = i;
            while(wolny[kolejny]){
                cykl[ncykl++] = kolejny;
                wolny[kolejny] = false;
                kolejny = cel[kolejny];
            }
            if (ncykl > 1) {
                int pary = ncykl / 2;
                for (int i = 0; i < pary; ++i) {
                    zamiany[ppol][0] = cykl[i];
                    zamiany[ppol][1] = cykl[ncykl-i-1];
                    ++ppol;
                }
            }
            dlmax = std::max(ncykl, dlmax);
        }
    }
    printf("%d\n", dlmax > 2 ? 2 : (dlmax == 2 ? 1 : 0));
    int cnt = 0;
    while(true) {
        if (ppol == 0) {
            break;
        } else {
            ++cnt;
            printf("%d\n", 2*ppol);
            for (int i = 0; i < ppol; ++i) {
                printf("%d ", zamiany[i][0]+1);
            }
            for (int i = ppol-1; i >= 0; --i) {
                printf("%d ", zamiany[i][1]+1);
            }
            putchar('\n');

            for (int i = 0; i < ppol; ++i) {
                std::swap(a[zamiany[i][0]], a[zamiany[i][1]]);
                std::swap(cel[zamiany[i][0]], cel[zamiany[i][1]]);
            }
            
        }
        for (int i = 0; i < n; ++i) {
            wolny[i] = true;
        }
        ppol = 0;
        for (int i = 0; i < n; ++i) {
            if (cel[i] == i)
                continue;
            if (wolny[i] && wolny[cel[i]]) {
                zamiany[ppol][0] = i;
                zamiany[ppol][1] = cel[i];
                ++ppol;
                wolny[i] = wolny[cel[i]] = false;
            }
        }
    }
    if (dlmax == 2) {
        assert (cnt == 1);
    } else if (dlmax == 1) {
        assert (cnt == 0);
    } else {
        assert (cnt == 2);
    }
}