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
133
134
135
136
137
138
139
140
141
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

#define N_MAX 3005

#define MP make_pair
#define PB push_back
#define FT first
#define SD second

int n,k;
int tmp;
int input[N_MAX];
int where[N_MAX];
int oo;
int output[N_MAX][N_MAX];
int outputlen[N_MAX];
int output_pref[N_MAX][N_MAX];
int outputlen_pref[N_MAX];
int cykle[N_MAX][N_MAX];
int clen[N_MAX];
bool used[N_MAX];
int cc;

vector<int> order;

void wypisz_cykle() {
  printf("==== CYKLE ====\n");
  for(int i=0;i<cc;i++){
    printf("Cykl %d:\n", i+1);
    for(int j=0;j<clen[i];j++) {
      printf("%d ", cykle[i][j]);
    }
    printf("\n");
  }
  printf("===== END CYKLE ====\n");
}

void wypisz_pozycje() {
  //input
  printf("==== INT ====\n");
  for(int i=0;i<n;i++) {
    printf("%d (%d) ", input[i], where[input[i]]);
  }
  printf("\n");
  printf("==== END INT ====\n");
}

void podziel_cykl(int nr, int left, int right) {
  int si = right/2;
  for(int i=0;i<(si+1)/2;i++) {
    //printf("Zamiana A: %d %d\n",cykle[nr][i],cykle[nr][si-i]);
    output_pref[oo][outputlen_pref[oo]++]=where[cykle[nr][i]];
    output[oo][outputlen[oo]++]=where[cykle[nr][si-i]];
  }
  for(int i=0;i<(right-si-1)/2;i++) {
    //printf("Zamiana B: %d %d\n",cykle[nr][si+1+i],cykle[nr][right-i-1]);
    output_pref[oo][outputlen_pref[oo]++]=where[cykle[nr][si+1+i]];
    output[oo][outputlen[oo]++]=where[cykle[nr][right-i-1]];
  }
}

int main()
{
  scanf("%d", &n);
  for(int i=0;i<n;i++) {
    scanf("%d", input+i);
    where[input[i]]=i;
    order.PB(input[i]);
  }
  //wypisz_pozycje();
  //sortowanie
  sort(order.begin(), order.end());
  /*for(int i=0;i<n;i++) {
    printf("%d ", order[i]);
  }
  printf("\n");
  */
  while(true) {
    //szukamy cykli
    int start;
    int iter;
    cc=0;
    for(int i=0;i<n;i++) used[order[i]]=0;
    for(int i=0;i<n;i++) {
      if(used[order[i]]) {
        continue;
      }
      used[order[i]]=1;
      if(where[order[i]]==i) {
        //wlasna pozycja
        continue;
      }
      //mamy cykl
      start=order[i];
      iter=i;
      clen[cc]=1;
      cykle[cc][0]=start;
      while(where[order[iter]]!=i) {
        cykle[cc][clen[cc]++] = order[where[order[iter]]];
        used[order[where[order[iter]]]]=1;
        iter=where[order[iter]];
      }
      cc++;
    }
    if(cc==0) break;
    //wypisz cykle
    //wypisz_cykle();
    //robimy iterację
    for(int i=0;i<cc;i++) {
      //dla każdego cyklu zmniejszamy go
      podziel_cykl(i,0,clen[i]);
    }
    //wykonujemy zamiany
    for(int i=0;i<outputlen_pref[oo];i++) {
      tmp=input[output_pref[oo][i]];
      input[output_pref[oo][i]]=input[output[oo][i]];
      where[input[output[oo][i]]]=output_pref[oo][i];
      input[output[oo][i]]=tmp;
      where[tmp]=output[oo][i];
    }
    //wypisz_cykle();
    //wypisz_pozycje();
    oo++;
    //break;
  }
  printf("%d\n", oo);
  for(int i=0;i<oo;i++) {
    printf("%d\n", 2*outputlen_pref[i]);
    for(int j=0;j<outputlen_pref[i];j++) {
      printf("%d ", output_pref[i][j]+1);
    }
    for(int j=outputlen[i]-1;j>=0;j--) {
      printf("%d ", output[i][j]+1);
    }
    printf("\n");
  }
  return 0;
}