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

const int N = 3000;
int n, x[N], ord[N];
bool u[N];
std::vector<std::pair<int, int> > ans[2];

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

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", x + i);
		ord[i] = i;
	}
	std::sort(ord, ord + n, cmp);
	for (int i = 0; i < n; ++i) if (ord[i] != i && !u[i]) {
		int cur = i;
		std::vector<int> cyc;
		do {
			u[cur] = 1;
			cyc.push_back(cur);
			cur = ord[cur];
		} while (cur != i);
		if (cyc.size() == 2) ans[0].push_back(std::make_pair(cur, ord[cur]));
		else {
			for (int i = 0; 2 * i + 1 < cyc.size(); ++i) ans[1].push_back(std::make_pair(cyc[i], cyc[(int)cyc.size() - i - 1]));
			for (int i = 1; 2 * i < cyc.size(); ++i) ans[0].push_back(std::make_pair(cyc[i], cyc[(int)cyc.size() - i]));
		}
	}
	if (ans[0].empty()) printf("0\n");
	else if (ans[1].empty()) printf("1\n");
	else printf("2\n");
	for (int i = 0; i < 2 && !ans[i].empty(); ++i) {
		printf("%d\n", (int)ans[i].size() * 2);
		for (int j = 0; j < (int)ans[i].size(); ++j) printf("%d ", ans[i][j].first + 1);
		for (int j = (int)ans[i].size() - 1; j >= 0; --j) printf("%d ", ans[i][j].second + 1);
		printf("\n");
		for (int j = 0; j < (int)ans[i].size(); ++j) std::swap(x[ans[i][j].first], x[ans[i][j].second]);
	}
	for (int i = 0; i + 1 < n; ++i) assert(x[i] < x[i + 1]);
	return 0;
}