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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, l, r) for (auto i = (l); i <= (r); ++i)
#define REP(i, n) FOR (i, 0, (n)-1)
#define ssize(x) int(x.size())
template<class A, class B>
auto&
operator<<(ostream& o, pair<A, B> p)
{
  return o << "(" << p.first << ", " << p.second << ")";
}
template<class T>
auto
operator<<(ostream& o, T x) -> decltype(x.end(), o)
{
  o << "{";
  int i = 0;
  for (auto e : x) o << (", ") + 2 * !i++ << e;
  return o << "}";
}
#ifdef DEBUG
#define debug(x...)                                                            \
  cerr << "[" #x "]: ", [](auto... $) { ((cerr << $ << "; "), ...); }(x),      \
    cerr << '\n'
#else
#define debug(...)                                                             \
  {                                                                            \
  }
#endif

// Global variables
int n;
vector<int> seq;
vector<int> rseq;

void input();

int
main()
{
  cin.tie(0)->sync_with_stdio(0);
  input();

  // Case 1: seq is already sorted
  if (is_sorted(seq.begin(), seq.end()))
  {
    cout << "0\n";
    return 0;
  }

  // Make all connected components of size at most 2
  deque<int> out1;
  vector<bool> visited(n);
  auto sp = [&visited](deque<int>& out, int a, int b)
  {
    visited[a] = true;
    visited[b] = true;
    swap(seq[a], seq[b]);
    swap(rseq[seq[a]], rseq[seq[b]]);
    out.push_front(a);
    out.push_back(b);
  };
  REP (start, n)
    if (!visited[start])
    {
      int ccsize = 1;
      for (int v = start; seq[v] != start; v = seq[v]) ccsize++;
      if (ccsize <= 2)
        continue;
      if (ccsize & 1)
        sp(out1, start, seq[start]);  // make ccsize even
      for (int v = rseq[start]; !visited[v] && seq[seq[v]] != v; v = rseq[v])
        sp(out1, v, seq[seq[v]]);
    }

  // Swap elements in components of two elements
  deque<int> out2;
  visited = vector<bool>(n);
  REP (v, n)
    if (!visited[v] && seq[v] != v)
      sp(out2, v, seq[v]);

  // Output
  if (!out1.empty())
  {
    cout << "2\n";
    cout << out1.size() << "\n";
    for (auto o : out1) cout << o + 1 << " ";
    cout << "\n";
  }
  else
    cout << "1\n";
  cout << out2.size() << "\n";
  for (auto o : out2) cout << o + 1 << " ";
  cout << "\n";
  return 0;
}

void
input()
{
  // Input
  cin >> n;
  vector<pair<int, int>> sorted(n);
  REP (i, n)
  {
    int val;
    cin >> val;
    sorted[i] = {val, i};
  }

  // Shrink values
  sort(sorted.begin(), sorted.end());
  seq.resize(n);
  rseq.resize(n);
  REP (i, n)
  {
    seq[sorted[i].second] = i;
    rseq[i] = sorted[i].second;
  }
  debug(seq, rseq);
}