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
#include <bits/stdc++.h>

using namespace std;

int n;
int t[3003];
int t2[3003];
bool czy[3003];
int perm[3003];
vector<vector<int>> res;

bool IsSorted() {
  for (int i = 2; i <= n; ++i) {
    if (t[i] < t[i - 1]) {
      return false;
    }
  }
  return true;
}

int main() {
  scanf("%d", &n);

  vector<int> v;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &t[i]);
    v.push_back(t[i]);
  }
  sort(v.begin(), v.end());

  int kCnt = 1;
  for (auto x : v) {
    perm[x] = kCnt;
    ++kCnt;
  }
  for (int i = 1; i <= n; ++i) {
    t[i] = perm[t[i]];
    // printf("%d ", t[i]);
  }
  // printf("\n");

  for (int i = 1; i <= n; ++i) {
    czy[i] = false;
    t2[i] = t[i];
  }
  vector<int> pocz, kon;
  vector<vector<int>> permutation_cycles;
  for (int i = 1; i <= n; ++i) {
    if (czy[i] || t[i] == i || czy[t[i]]) {
      continue;
    }
    int w = i;
    vector<int> permutation;
    do {
      permutation.push_back(w);
      czy[w] = true;
      w = t[w];
    } while (w != i);
    permutation.pop_back();
    if (permutation.size() % 2 == 1) {
      permutation.erase(permutation.begin() + permutation.size() / 2);
    }
    if (!permutation.empty()) {
      // printf("PERM :: ");
      // for (auto x : permutation) {
      //   printf("%d ", x);
      // }
      // printf("\n");
      permutation_cycles.push_back(permutation);
    }
  }

  for (auto cycle : permutation_cycles) {
    for (int i = 0; i < cycle.size() / 2; ++i) {
      pocz.push_back(cycle[i]);
    }
    for (int i = cycle.size() - 1; i >= cycle.size() / 2; --i) {
      kon.push_back(cycle[i]);
    }
  }
  vector<int> pom = pocz;
  for (int i = kon.size() - 1; i >= 0; --i) {
    pom.push_back(kon[i]);
  }
  if (!pom.empty()) {
    res.push_back(pom);
  }
  assert(pom.size() % 2 == 0);
  for (int i = 0; i < pom.size() / 2; ++i) {
    swap(t[pom[i]], t[pom[pom.size() - i - 1]]);
  }
  // printf("\n");
  // }
  if (!IsSorted()) {
    pocz.clear();
    kon.clear();
    for (int i = 1; i <= n; ++i) {
      czy[i] = false;
    }
    for (int i = 1; i <= n; ++i) {
      if (t[i] == i || czy[i] || czy[t[i]]) {
        continue;
      }
      czy[i] = true;
      czy[t[i]] = true;
      pocz.push_back(i);
      kon.push_back(t[i]);
    }
    vector<int> pom = pocz;
    for (int i = kon.size() - 1; i >= 0; --i) {
      pom.push_back(kon[i]);
    }
    if (!pom.empty()) {
      res.push_back(pom);
    }
    for (int i = 0; i < pom.size() / 2; ++i) {
      swap(t[pom[i]], t[pom[pom.size() - i - 1]]);
    }
  }
  assert(IsSorted());

  printf("%d\n", res.size());
  for (auto x : res) {
    printf("%d\n", x.size());
    for (auto c : x) {
      printf("%d ", c);
    }
    printf("\n");
  }

  // printf("SORTED %d :: ", IsSorted());
  // for (int i = 1; i <= n; ++i) {
  //   printf("%d ", t[i]);
  // }
}