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
// 2022-3-fot-fotografia.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>

constexpr int MAXN = 1e5;

std::vector<std::pair<int, int> > fst;
std::vector<std::pair<int, int> > snd;

bool handled[MAXN];
int t[MAXN];
int ttmp[MAXN];

void handlev(std::vector<int>& v) {
	for (auto i : v) {
		handled[i] = true;
	}
	if (v.size() <= 1) {
		return;
	}
	if (v.size() == 2) {
		fst.push_back(std::make_pair(v[0], v[1]));
		return;
	}

	fst.push_back(std::make_pair(v[0], v[1]));
	int n = v.size();
	for (int i = 0; i < (n - 2) / 2; i++) {
		fst.push_back(std::make_pair(v[i + 2], v[n - 1 - i]));
	}
	snd.push_back(std::make_pair(v[0], v[2]));
	for (int i = 0; i + 3 < n - 1 - i; i++) {
		snd.push_back(std::make_pair(v[i + 3], v[n - 1 - i]));
	}
}

void prnt(std::vector<std::pair<int, int> >& v) {
	std::cout << 2 * v.size() << '\n';
	for (int i = 0; i < v.size(); i++) {
		std::cout << v[i].first + 1 << ' ';
	}
	for (int i = v.size() - 1; i >= 0; i--) {
		std::cout << v[i].second + 1 << ' ';
	}
	std::cout << '\n';
}

int main()
{
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);

	int n;
	std::cin >> n;

	for (int i = 0; i < n; i++) {
		std::cin >> t[i];
		ttmp[i] = t[i];
	}
	
	// normalize@begin
	std::sort(ttmp, ttmp + n);
	std::map<int, int> mp;

	for (int i = 0; i < n; i++) {
		mp[ttmp[i]] = i;
	}
	for (int i = 0; i < n; i++) {
		t[i] = mp[t[i]];
	}
	// normalize@end

	std::vector<int> v;
	for (int i = 0; i < n; i++) {
		if (handled[i]) {
			continue;
		}
		v.clear();
		v.push_back(i);
		for (int j = t[i]; j != i; j = t[j]) {
			v.push_back(j);
		}
		handlev(v);
	}

	if (fst.size() == 0) {
		std::cout << "0\n";
		return 0;
	}
	if (snd.size() == 0) {
		std::cout << "1\n";
		prnt(fst);
		return 0;
	}
	std::cout << "2\n";
	prnt(fst);
	prnt(snd);
	return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file