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

#include <vector>

std::vector<int> getIndexes(std::vector<int>& data) {
  std::vector<bool> sortedData(3001);
  for (const auto& value : data) {
    sortedData[value] = true;
  }
  std::vector<int> indexes(3001);
  int index = 1;
  for (int i = 1; i <= 3000; ++i) {
    if (sortedData[i]) {
      indexes[i] = index++;
    }
  }
  return indexes;
}

void swap(std::vector<int>& data, const std::vector<int>& indexes, bool& work, std::vector<bool>& swaped, std::vector<int>& moves1, std::vector<int>& moves2, const int elementIndex, int distance) {
  int swapElementIndex = elementIndex;
  while (0 < distance) {
    swapElementIndex = indexes[data[swapElementIndex]];
    distance--;
  }
  if (swaped[data[elementIndex]] || swaped[data[swapElementIndex]]) {
    return;
  }
  work = true;
  moves1.push_back(elementIndex);
  moves2.push_back(swapElementIndex);
  std::swap(data[elementIndex], data[swapElementIndex]);
  swaped[data[elementIndex]] = true;
  swaped[data[swapElementIndex]] = true;
}

std::vector<int> getStep(std::vector<int>& data, const std::vector<int>& indexes) {
  std::vector<bool> swaped(3001);
  std::vector<int> moves1;
  std::vector<int> moves2;
  bool work = true;
  while (work) {
    work = false;
    for (int i = 1; i < data.size(); ++i) {
      auto element = data[i];
      if (!swaped[element]) {
        int length = 1;
        while (indexes[element] != i) {
          element = data[indexes[element]];
          length++;
        }
        if (2 <= length) {
          swap(data, indexes, work, swaped, moves1, moves2, i, length / 2);
        }
      }
    }
  }
  std::move(moves2.rbegin(), moves2.rend(), std::back_inserter(moves1));
  return moves1;
}

int main() {
  int n;
  scanf("%d\n", &n);
  std::vector<int> data(n + 1);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &data[i]);
  }
  const auto indexes = getIndexes(data);
  std::vector<std::vector<int>> moves;
  while (true) {
    const auto step = getStep(data, indexes);
    if (step.empty()) {
      break;
    } else {
      moves.push_back(step);
    }
  }
  printf("%lu\n", moves.size());
  for (const auto& step : moves) {
    printf("%lu\n", step.size());
    for (const auto& value : step) {
      printf("%d ", value);
    }
    printf("\n");
  }
  return 0;
}