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
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

const int MN = 3e3 + 5LL;
int tab[MN];
int pl[MN];
vector<pair<int,int> >P;
vector<int>V;
vector<vector<int> > res;
vector<int>ans;
stack<int>S;
bool vis[MN];

bool ok(int n)
{
    for(int i = 1; i <= n; i++)
        if(V[i] != i) return false;
    return true;
}

int main()
{
    BOOST;
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        int a;
        cin>>a;
        P.push_back({a,i});
    }
    sort(P.begin(),P.end());
    for(int i = 1; i <= n; i++)
    {
        tab[P[i-1].nd] = i;
        pl[i] = P[i-1].nd;
    }
    V.push_back(0);
    for(int i = 1; i <= n; i++) V.push_back(tab[i]);
    while(!ok(n))
    {
        ans.clear();
        for(int i = 1; i <= n; i++) vis[i] = 0;
        for(int i = 1; i <= n; i++)
        {
            if(pl[i] != i)
            {
                if(pl[pl[i]] == i)
                {
                    if(!vis[i] && !vis[pl[i]])
                    {
                        vis[i] = 1;
                        vis[pl[i]] = 1;
                        ans.push_back(pl[i]);
                        S.push(i);
                        pl[V[i]] = pl[i];
                        swap(V[i],V[pl[i]]);
                        pl[i] = i;
                    }
                }
                else
                {
                    if(!vis[i] && !vis[pl[pl[i]]])
                    {
                        vis[i] = 1;
                        vis[pl[pl[i]]] = 1;
                        ans.push_back(i);
                        S.push(pl[pl[i]]);
                        int A = i, B = pl[pl[i]];
                        pl[V[i]] = pl[pl[i]];
                        pl[V[pl[pl[i]]]] = i;
                        swap(V[A],V[B]);
                    }
                }
            }
        }
        while(!S.empty())
        {
            ans.push_back(S.top());
            S.pop();
        }
        res.push_back(ans);
    }
    cout<<res.size()<<'\n';
    for(int i = 0; i < res.size(); i++)
    {
        cout<<res[i].size()<<'\n';
        for(int j = 0; j < res[i].size(); j++) cout<<res[i][j]<<' ';
        cout<<'\n';
    }
    return 0;
}