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
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <vector>

using namespace std;

void map_values(vector<int> &h) {
  int nr = 0;
  map<int, int> m;
  set<int> s;
  for (auto x : h)
    s.emplace(x);
  for (auto x : s)
    m[x] = nr++;
  for (auto &x : h)
    x = m[x];
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  vector<int> h(n);
  for (auto &x : h)
    cin >> x;

  map_values(h);
  int max_cyc = 0;

  vector<bool> visited(n, false);
  for (int i = 0; i < n; i++) {
    if (visited[i])
      continue;
    int j = i;
    int cnt = 0;
    while (!visited[j]) {
      visited[j] = true;
      j = h[j];
      cnt++;
    }
    max_cyc = max(max_cyc, cnt);
  }

  if (max_cyc == 1) {
    cout << "0\n";
  } else if (max_cyc == 2) {
    cout << "1\n";
    list<int> l;
    vector<bool> used(n, false);
    for (int i = 0; i < n; i++) {
      if (used[i])
        continue;
      if (h[i] != i) {
        l.push_back(i);
        l.push_front(h[i]);
        used[i] = true;
        used[h[i]] = true;
      }
    }
    cout << l.size() << '\n';
    for (auto x : l)
      cout << x + 1 << ' ';
  } else {
    cout << "2\n";
  }
}