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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <list>

int arr[3001], arr2[3001], arr3[3001];

void swap(int* a, int* b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int main() {
  int n;
  scanf("%d", &n);
  for(int i=0;i<n;i++)
    scanf(" %d", arr + i);
  memcpy(arr2, arr, sizeof(arr));
  std::sort(arr2, arr2+n);
  int toswap = 0;
  for(int i=0;i<n;i++) {
    arr3[arr[i]] = i;
  }

  int beg = 0;
  std::list<int> ans;
  int lans = 0;
  while(beg < n-1) {
    char used[3001] = {0};
    int tmp[3000];
    int ntmp = 0;
    for(int i=beg;i<n;i++) {
      if(arr[i] == arr2[i])
        beg++;
      else if(!used[arr2[i]] && !used[arr[i]]) {
        int p1 = arr3[arr[i]], p2 = arr3[arr2[i]];
        int cur = arr[i];
        swap(&arr[i], &arr[arr3[arr2[i]]]);
        arr3[cur] = arr3[arr2[i]];
        arr3[arr2[i]] = i;
        used[cur] = 1;
        used[arr2[i]] = 1;
        beg++;
        tmp[2*ntmp] = p1+1;
        tmp[2*ntmp+1] = p2+1;
        ntmp++;
      }
    }
    ans.push_back(ntmp*2);
    for(int i=0;i<ntmp; i++) {
      ans.push_back(tmp[2*i]);
    } 
    int _n = ntmp*2;
    for(int i=0;i<ntmp; i++) {
      ans.push_back(tmp[_n-1-2*i]);
    } 
    lans++;
  }
  printf("%d\n", lans);
  std::list<int>::iterator it = ans.begin();
  for(int i=0;i<lans;i++) {
    int l = *it;
    printf("%d\n", l);
    for(int j=0;j<l;j++) {
      it++;
      printf("%d ", *it);
    } putchar(10);
    it++;
  }
}