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

const bool debug = false;
using namespace std;

pair<int,int> t[1000111];
int h[1000111];
bool isSorted(int h[], int n) {
  for (int i = 2; i <= n; i++) if (h[i-1] > h[i]) return false;
  return true;
}

vector<vector<int>> results;

bool visited[1000111];


void dfs(vector<int>& cycleAcc, int h[], bool visited[], int i) {
  if (debug) printf("DFS step %d\n", i);
  if (visited[i]) return;
  visited[i] = true;
  cycleAcc.push_back(i);
  dfs(cycleAcc, h, visited, h[i]);
}

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

  for (int i = 1; i <= n; i++) {
    int a;
    scanf("%d", &a);
    t[i] = {a, i};
  }

  sort(t+1, t+n+1);

  for (int i = 1; i <= n; i++) {
    t[i] = {t[i].second, i};
  }
  sort(t+1, t+n+1);

  if (debug) printf("reduced\n");
  for (int i = 1; i <= n; i++){
    h[i] = t[i].second;
    if (debug) printf("%d ", h[i]);
  }
  if (debug) printf("\n\n");

  for (int assertt = 0; assertt < 4; assertt++) {
    if (debug) printf("LOOP START assert %d\n", assertt);
    if (debug) printf("stan");
    if (debug) for (int i = 1; i <= n; i++) printf("%d ", h[i]);
    if (debug) printf("\n");

    if (isSorted(h, n)) {
      printf("%lu\n", results.size());
      for (auto it : results) {
        printf("%lu\n", it.size());
        for (auto it2 : it) {
          printf("%d ", it2);
        }
        printf("\n");
      }
      return 0;
    }

    for (int i = 1; i <= n; i++) visited[i] = false;

    vector<int> resultPrefix, resultSuffix, fullResult;
    resultPrefix.clear();
    resultSuffix.clear();
    fullResult.clear();

    for (int i = 1; i <= n; i++) {
      if (visited[i]) continue;
      if (h[i] == i) continue;
      vector<int> currentCycle;
      currentCycle.clear();
      dfs(currentCycle, h, visited, i);

      if (debug) printf("currentCycle %lu \n", currentCycle.size());
      if (debug) for (auto it : currentCycle) printf("%d ", it);
      if (debug) printf("\n");

      int endJ = currentCycle.size() / 2;
      for (int j = 0; j < endJ; j++) resultPrefix.push_back(currentCycle[j]);

      endJ = (currentCycle.size() + 1) / 2;
      for (int j = currentCycle.size()-1; j >= endJ; j--) resultSuffix.push_back(currentCycle[j]);
    }

    if (debug) printf("po dfsach, %lu %lu\n", resultPrefix.size(), resultSuffix.size());

    if (debug) for (auto it : resultPrefix) printf("%d ", it);
    if (debug) printf("\n");
    if (debug) for (auto it : resultSuffix) printf("%d ", it);
    if (debug) printf("\n");

    for (int i = 0; i < resultPrefix.size(); i++) fullResult.push_back(resultPrefix[i]);
    for (int i = resultSuffix.size() - 1; i >= 0; i--) fullResult.push_back(resultSuffix[i]);

    if (debug) printf("fullResult %lu\n", fullResult.size());
    if (debug) for (auto it : fullResult) printf("%d ", it);
    if (debug) printf("\n");

    for (int i = 0; i < fullResult.size() / 2; i++) {
      int oppositeI = fullResult.size() - 1 - i;
      swap(h[fullResult[i]], h[fullResult[oppositeI]]);
    }
    results.push_back(fullResult);
    if (debug) printf("results %lu\n", results.size());
  }


  
  return 0;
}