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
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>

const int max_n = 5000;

int n, step;
int a[max_n];
int b[max_n];
std::map<int, int> mm;


int m[2];
int left[2][max_n];
int right[2][max_n];

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  std::sort(b, b + n);
  for (int i = 0; i < n; ++i) mm[b[i]] = i;
  for (int i = 0; i < n; ++i) a[i] = mm[a[i]];
  step = 0;
  m[0] = m[1] = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] != -1 && a[i] != i) {
      std::vector<int> current;
      int start = a[i];
      a[i] = -1;
      while (start != -1) {
        current.push_back(start);
        int tmp = a[start];
        a[start] = -1;
        start = tmp;
      }
      for (int j = 0; j < current.size() / 2; ++j) {    
        left[0][m[0]] = current[j] + 1;
        right[0][m[0]++] = current[current.size() - j - 1] + 1;
        std::swap(current[j], current[current.size() - j - 1]);
      }
      if (current.size() > 2) {
        for (int j = 0; j < (current.size() - 1) / 2; ++j) {    
          left[1][m[1]] = current[j] + 1;
          right[1][m[1]++] = current[current.size() - j - 2] + 1;
          std::swap(current[j], current[current.size() - j - 2]);
        }    
      }
    }
  }
  if (m[0] == 0) {
    printf("0\n");
    return 0;
  }
  printf("%d\n", 1 + (m[1] > 0));
  printf("%d\n", 2 * m[0]);
  for (int i = 0; i < m[0]; ++i) {
    printf("%d ", left[0][i]);
  }
  for (int i = m[0] - 1; i >= 0; --i) {
    printf("%d ", right[0][i]);
  }
  printf("\n");
  if (m[1] > 0) {
    printf("%d\n", 2 * m[1]);
    for (int i = 0; i < m[1]; ++i) {
      printf("%d ", left[1][i]);
    }
    for (int i = m[1] - 1; i >= 0; --i) {
      printf("%d ", right[1][i]);
    }
    printf("\n");
  }

  return 0;
}