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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 3005;
const bool CHECK = false;

int i, n, j, kol[N], which[N], tab[N], vis[N];
VI v, vNew, v1, v2;
vector<VI> vs;
bool big;

bool cmp(int a, int b) {
	return tab[a] < tab[b];
}

void loop() {
	int a = 1;
	while (a < 10) {
		a++;
		a--;
	}
}

void check() {
	printf("check\n");
	for (i=0;i<n;i++) printf("%d\n", tab[i]);
	for (i=1;i<n;i++) if (tab[i - 1] >= tab[i]) loop();
}

void print() {
	printf("%d\n", v1.size() * 2);
	for (int i=0;i<v1.size();i++) printf("%d ", v1[i] + 1);
	for (int i=v2.size() - 1;i>=0;i--) printf("%d ", v2[i] + 1);
	printf("\n");
	if (CHECK) for (i=0;i<v1.size();i++) swap(tab[v1[i]], tab[v2[i]]);
}

int main() {
scanf("%d", &n);
for (i=0;i<n;i++) {
	scanf("%d", &tab[i]);
	kol[i] = i;
	vis[i] = 0;
}
sort(kol, kol + n, cmp);
for (i=0;i<n;i++) which[kol[i]] = i;
vs.clear();
big = false;
for (i=0;i<n;i++) if (!vis[i]) {
	j = i;
	v.clear();
	while (true) {
		v.pb(j);
		vis[j] = 1;
		j = which[j];
		if (j == i) break;
	}
	if (v.size() > 1) vs.pb(v);
	if (v.size() > 2) big = true;
}
if (vs.size() == 0) {
	printf("0\n");
	return 0;
}
if (!big) {
	printf("1\n");
	v1.clear();
	v2.clear();
	for (auto& vv : vs) {
		v1.pb(vv[0]);
		v2.pb(vv[1]);
	}
	print();
	return 0;
}

printf("2\n");
v1.clear();
v2.clear();
for (auto& vv : vs) {
	i = 1;
	j = vv.size() - 1;
	while (i < j) {
		v1.pb(vv[i]);
		v2.pb(vv[j]);
		i++;
		j--;
	}
}
print();
v1.clear();
v2.clear();
for (auto& vv : vs) {
	v1.pb(vv[0]);
	v2.pb(vv[1]);
	i = 2;
	j = vv.size() - 1;
	while (i < j) {
		v1.pb(vv[i]);
		v2.pb(vv[j]);
		i++;
		j--;
	}
}
print();
if (CHECK) check();
return 0;
}