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

using namespace std;



vector<vector<int>> to_cycles(vector<int> &perm) {
  vector<vector<int>> cycles;
  vector<bool> vis(perm.size());
  for (auto x : perm) {
    if (!vis[x]) {
      vector<int> cycle = { x };
      vis[x] = true;
      int y = perm[x];
      while (y != x) {
        vis[y] = true;
        cycle.push_back(y);
        y = perm[y];
      }
      cycles.push_back(cycle);
    }
  }
  return cycles;
}

// split cycle into two involutions and put them at the back of A, B
void split_cycle(const vector<int> &cycle, vector<pair<int, int>> &A, vector<pair<int, int>> &B) {
  if (cycle.size() == 1) return;
  if (cycle.size() == 2) {
    A.push_back({ cycle[0], cycle[1] });
    return;
  }

  // (1 2 3 4 5 .. k) = (1 k) (2 k-1) (3 k-2) ... then (k 2) (k-1 3) (k-2 4) ...
  for (int i = 0; i < (int)cycle.size() / 2; i++) {
    A.push_back({ cycle[i], cycle[cycle.size() - 1 - i] });
  }
  for (int i = 0; i < ((int)cycle.size() - 1) / 2; i++) {
    B.push_back({ cycle[cycle.size() - 1 - i], cycle[i + 1] });
  }
}

void print_invol(const vector<pair<int, int>> &I) {
  if (I.size() == 0) return;
  printf("%d\n", 2 * I.size());
  for (int i = 0; i < (int)I.size(); i++)      printf("%d ", I[i].first + 1);
  for (int i = (int)I.size() - 1; i >= 0; i--) printf("%d ", I[i].second + 1);
  puts("");
}



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

  vector<pair<int, int>> h(n);
  for (int i = 0; i < n; i++) {
    h[i].second = i;
    scanf("%d", &h[i].first);
  }
  sort(h.begin(), h.end());
  vector<int> perm(n);
  for (int i = 0; i < n; i++) {
    perm[h[i].second] = i;
  }

  auto cycles = to_cycles(perm);
  vector<pair<int, int>> A; // first involution
  vector<pair<int, int>> B; // second involution
  for (auto &cycle : cycles) {
    split_cycle(cycle, A, B);
  }

  puts(A.size() == 0 ? "0" : B.size() == 0 ? "1" : "2");
  print_invol(A);
  print_invol(B);
}