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>

#ifdef DEBUG_LEVEL
#warning "debug is enabled"
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
	int n;
	cin >> n;
	vector<pair<int, int>> rawData(n);
	vector<int> data(n);
	vector<int> lookup(n);
	for (int i = 0; i < n; i++) {
		cin >> rawData[i].first;
		rawData[i].second = i;
	}
	sort(rawData.begin(), rawData.end());
	for (int i = 0; i < n; i++) {
		data[rawData[i].second] = i;
		lookup[i] = rawData[i].second;
	}
#if DEBUG_LEVEL > 2
	for (auto d : data)
		cerr << d << " ";
	cerr << "\n";
#endif

	bool isSorted = true;
	for (int i = 1; i < n; i++) {
		if (data[i-1] >= data[i]) {
			isSorted = false;
			break;
		}
	}

	if (isSorted) {
		cout << "0\n";
		return 0;
	}
	
	vector<pair<int, int>> pass;
	set<int> takenNums;
	set<int> takenInds;

	for (int i = 0; i < n; i++) {
		if (data[i] == i
				|| takenNums.find(i) != takenNums.end()
				|| takenInds.find(i) != takenInds.end()) {
			continue;
		}
		int idx = lookup[i];
		if (takenInds.find(idx) != takenInds.end()) {
			continue;
		}
		takenInds.insert(i);
		takenInds.insert(idx);
		takenNums.insert(i);
		takenNums.insert(data[i]);
		pass.push_back({i, idx});
	}

	isSorted = true;
	for (auto p : pass) {
		swap(data[p.first], data[p.second]);
		swap(lookup[data[p.second]], lookup[data[p.first]]);
	}
	for (int i = 1; i < n; i++) {
		if (data[i-1] > data[i]) {
			isSorted = false;
			break;
		}
	}

	cout << (isSorted ? 1 : 2)
			 << "\n"
			 << pass.size()*2
			 << "\n";
	for (int i = 0; i < pass.size(); i++) {
		cout << pass[i].first+1 << " ";
	}
	for (int i = pass.size()-1; i >= 0; i--) {
		cout << pass[i].second+1 << " ";
	}
	if (isSorted) {
		return 0;
	}
	pass.clear();
	takenInds.clear();
	for (int i = 0; i < n; i++) {
		if (data[i] == i
				|| takenInds.find(i) != takenInds.end()) {
			continue;
		}
		pass.push_back({i, lookup[i]});
		takenInds.insert(i);
		takenInds.insert(lookup[i]);
	}	
	cout << "\n"
			 << pass.size()*2
			 << "\n";
	for (int i = 0; i < pass.size(); i++) {
		cout << pass[i].first+1 << " ";
	}
	for (int i = pass.size()-1; i >= 0; i--) {
		cout << pass[i].second+1 << " ";
	}
	return 0;
}