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 <bits/stdc++.h>
using namespace std;

int n, t[3001], nr[3001], p[3001], us[3001], ti, l1[3001], l2[3001];
bool ct[3001];
vector <vector <int> > res;

void in()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &t[i]);

        ct[t[i]] = 1;
    }

    n = 0;
    for(int i = 1; i <= 3001; ++i)
    {
        if(ct[i])
            nr[i] = ++n;
    }

    for(int i = 1; i <= n; ++i)
        t[i] = nr[t[i]];
}

void calc()
{
    for(int i = 1; i <= n; ++i)
        p[t[i]] = i;

    for(ti = 1; ; ++ti)
    {
        int m = 0;

        for(int i = 1; i <= n; ++i)
        {
            if(t[i] == i)
                continue;

            if((us[i] ^ ti) && (us[p[i]] ^ ti) && t[i] == p[i])
            {
                us[i] = us[p[i]] = ti;
                l1[m] = i;
                l2[m] = p[i];
                m++;

                swap(t[i], t[p[i]]);
                swap(p[t[i]], p[t[p[i]]]);
            }
        }


        for(int i = 1; i <= n; ++i)
        {
            if(t[i] == i)
                continue;

            if((us[i] ^ ti) && (us[p[i]] ^ ti))
            {
                us[i] = us[p[i]] = ti;
                l1[m] = i;
                l2[m] = p[i];
                m++;

                swap(t[i], t[p[i]]);
                swap(p[t[i]], p[t[p[i]]]);
            }
        }

        if(m == 0)
            break;

        res.push_back(vector <int>(m << 1));
        for(int i = 0; i < m; ++i)
        {
            res.back()[i] = l1[i];
            res.back()[(m << 1) - i - 1] = l2[i];
        }
    }
}

void out()
{
    printf("%d\n", int(res.size()));
    for(auto &i : res)
    {
        printf("%d\n", int(i.size()));
        for(auto &j : i)
            printf("%d ", j);
        printf("\n");
    }
}

int main()
{
    in();
    calc();
    out();
}