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
#include <bits/stdc++.h>
using namespace std;
const int N = 3001;
int n, t[N];
vector<int> v[2], tmp;
vector<pair<int, int>> sortv;
int q;
bool w[N];

bool red() {
  bool ok = true;
  sort(sortv.begin(), sortv.end());
  for (int i = 0; i < n; i++) {
    int p = sortv[i].second;
    t[p] = i;
    if (t[i] != i) {
      ok = false;
    }
  }
  return ok;
}

int main()
{
  ios_base::sync_with_stdio(0);

  cin >> n;

  for (int i = 0; i < n; i++) {
    cin >> t[i];
    sortv.push_back(make_pair(t[i], i));
  }
  bool ok = red();

  if (ok) {
    cout << 0 << endl;
    return 0;
  }

  fill(w, w + n, false);

  for (int i = 0; i < n; i++) {
    if (w[i]) {
      continue;
    }
    int l = 0, a = i;
    do {
      w[a] = true;
      a = t[a];
      l++;
    }
    while (a != i);

    if (l == 2) {
      v[0].push_back(i);
      v[1].push_back(t[i]);
    }
    if (l <= 2) {
      continue;
    }

    int pary = (l - 1) / 2;

    a = t[a];
    for (int x = 0; x < pary; x++) {
      v[0].push_back(a);
      a = t[a];
    }
    if (l % 2 == 0) {
      a = t[a];
    }
    for (int x = 0; x < pary; x++) {
      tmp.push_back(a);
      a = t[a];
    }
    while(!tmp.empty()) {
      v[1].push_back(tmp.back());
      tmp.pop_back();
    }
  }

  for (int i = 0; i < v[0].size(); i++) {
    swap(t[v[0][i]], t[v[1][i]]);
  }

  int q = 0;
  for (int i = 0; i < n; i++) {
    if (t[i] != i) {
      q++;
    }
  }

  if (q == 0) {
    cout << "1" << endl;
  } else {
    cout << "2" << endl;
  }

  cout << v[0].size() + v[1].size() << endl;
  for (int i = 0; i < v[0].size(); i++) {
    cout << v[0][i] + 1 << " ";
  }
  while (!v[1].empty()) {
    cout << v[1].back() + 1 << " ";
    v[1].pop_back();
  }
  cout << endl;

  if (q > 0) {
    cout << q << endl;

    for (int i = 0; i < n; i++) {
      if (t[i] != i) {
        cout << i + 1 << " ";
        v[1].push_back(t[i]);
        swap(t[t[i]], t[i]);
      }
    }
    while (!v[1].empty()) {
      cout << v[1].back() + 1 << " ";
      v[1].pop_back();
    }
    cout << endl;
  }

  return 0;
}