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
#include <stdio.h>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
int n;
std::vector<int> m1;

void prepare(const std::vector<int>& v)
{
    auto sorted = v;
    std::unordered_map<int, int> pos;
    m1.resize(n);
    for(auto i =0 ;i<v.size();i++)
	pos[v[i]]= i;
    std::sort(sorted.begin(), sorted.end());
    for(int i =0;i<sorted.size();i++)
    {
	m1[i] = pos[sorted[i]];
    }
}
int cykl[3500]={};

int main()
{
    scanf("%d",&n);
    std::vector<int> v(n);
    for(int i =0;i<n;i++)
	scanf("%d",&v[i]);
    
    prepare(v);
    std::vector<std::vector<int>>  cykle;
    int curCykl = 1;
    for(int i =0;i<n;i++)
    {
	std::vector<int> tmp;
	auto cur = i;
	while(cykl[cur] == 0)
	{
	    tmp.push_back(cur);
	    cykl[cur] = curCykl;
	    cur = m1[cur];
	}
	if(tmp.size() > 0)
	{
	    cykle.push_back(tmp);
	    curCykl++;
	}
    }
    std::vector<std::vector<int>> res;

/*    for(int i =0;i<cykle.size();i++)
    {
	printf("CYKL ");
	for(int j=0;j<cykle[i].size();j++)
	    printf("%d ", cykle[i][j]);
	printf("\n");

    }*/
    while(1)
    {
	bool ok = true;
	std::vector<int> b, e;
	std::vector<int> round;
	for(int i=0;i<cykle.size();i++)
	{
	    if(cykle[i].size() <= 1)
	    {
		continue;
	    }
	    ok = false;
	    std::vector<int> tmp;
	    for(int j=0;j<cykle[i].size();j+=2)
	    {
		if(j+1 < cykle[i].size())
		{
		    b.push_back(cykle[i][j]);
		    e.push_back(cykle[i][j+1]);
		    tmp.push_back(cykle[i][j+1]);
		    std::swap(v[cykle[i][j]] ,v[cykle[i][j+1]]);
		}
		else
		{
		    tmp.push_back(cykle[i][j]);
		}
	    }
	    cykle[i] = tmp;
	}
	if(ok) break;
	for(int i =0;i<b.size(); i++)
		round.push_back(b[i]+1);
	for(int i =e.size()-1;i>=0;i--)
	    round.push_back(e[i]+1);
	res.push_back(round);
    }
    
    printf("%d\n",res.size());
    for(int  i=0;i<res.size();i++)
    {
        printf("%d\n",res[i].size());
        for(const auto&x : res[i])
            printf("%d ",x);

        printf("\n");
    }
    return 0;

}