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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int NN = 3003;
int tab[NN];
int sorted[NN];
int map[NN];
bool used[NN];

vector<vector<int>> cycles(int N) {
  vector<vector<int>> res;
  memset(used, 0, sizeof(bool) * NN);
  for (int i = 0; i < N; ++i) {
    int m = map[tab[i]];
    if (m != i && !used[i]) {
      vector<int> cycle = {i};
      for (; m != i; m = map[tab[m]]) {
        cycle.push_back(m);
        used[m] = true;
      }
      res.push_back(cycle);
    }
  }
  return res;
}

void easy_swaps(const vector<int> cycle, int start, int end, vector<pair<int, int>> &acc) {
  for (; end > start; --end, ++start) {
    acc.push_back({cycle[start], cycle[end]});
  }
}

void swaps(const vector<int> cycle, int start, int end, vector<pair<int, int>> &acc) {
  int len = end - start + 1;
  if (len <= 1) {
    return;
  } else if (2 <= len && len <= 3) {
    acc.push_back({cycle[start], cycle[end]});
  } else {
    int half = start + len / 2;
    acc.push_back({cycle[start], cycle[half - 1]});
    acc.push_back({cycle[half], cycle[end]});
    easy_swaps(cycle, start + 1, half - 2, acc);
    easy_swaps(cycle, half + 1, end - 1, acc);
  }
}

template <typename T> void swap(T *t, int a, int b) {
  T x = t[a];
  t[a] = t[b];
  t[b] = x;
}

int main() {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &tab[i]);
    sorted[i] = tab[i];
  }

  vector<vector<int>> lines;
  sort(sorted, sorted + N);
  for (int i = 0; i < N; ++i) {
    map[sorted[i]] = i;
  }

  while (true) {
    vector<vector<int>> c = cycles(N);
    if (c.empty()) {
      break;
    }
    vector<pair<int, int>> s;
    for (auto cycle : c) {
      swaps(cycle, 0, cycle.size() - 1, s);
    }

    vector<int> line;
    for (auto sw : s) {
      swap(tab, sw.first, sw.second);
      line.push_back(sw.first);
    }
    for (auto it = s.rbegin(); it != s.rend(); ++it) {
      line.push_back(it->second);
    }
    lines.push_back(line);
  }

  printf("%lu\n", lines.size());
  for (auto line : lines) {
    printf("%lu\n", line.size());
    for (int v : line) {
      printf("%d ", v + 1);
    }
    printf("\n");
  }

  return 0;
}