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
#include<bits/stdc++.h>
using namespace std;
int tab[3001],pos[3001], nr[3001] ={0},wyn[3001];
vector<int> cykl;

int main()
{
	ios_base::sync_with_stdio(0);
	int n, i, j,  k = 1, ile = 0, dl = 0;
	cin >> n;
	for(i = 1; i <= n; i++) {
		cin >> tab[i];
		pos[tab[i]] = 1;
	}
	i = 1;
	for(j = 1; j < 3001; j++) {
		if(pos[j] == 1) {
			pos[j] = i;
			i++;
		}
	}
	for(i = 1; i <= n; i++) {
		tab[i] = pos[tab[i]];
		if(tab[i] == i) nr[i] = 1;
	}
	//for(i = 1; i <= n; i++) cout << tab[i] <<" "; cout << endl;
	for(i = 1; i <= n; i++){
		cykl.clear();
		cykl.resize(0);
		if(nr[i] == 0) {
			int pocz = i;
			nr[i] = 1;
			cykl.push_back(i);
			while(tab[pocz]!= i) {
				pocz = tab[pocz];
				nr[pocz]= 1;
				cykl.push_back(pocz);
			}
			//for(j = 0; j < cykl.size(); j++) cout <<cykl[j] <<" "; cout << endl;
			for(j = 0; j < cykl.size()/2; j++){
				wyn[k] = cykl[j];
				wyn[n + 1 - k]= cykl[cykl.size() - 1 - j];
				dl += 2;
				swap(tab[wyn[k]],tab[wyn[n +1 -k]]);
				k++;
			}			
		}
	}
	for(i = 1; i <= n; i++) {
		if(tab[i] == i) ile++;
	}
	if(dl == 0) {
		cout  << 0 ;
		return 0;
	}
	if(ile == n) cout << 1 << endl;
	else cout<< 2 << endl;
	cout << dl << endl;
	for(i = 1; i <= n; i++) {
		if(wyn[i] > 0) {
			cout << wyn[i] <<" ";
		}
		wyn[i] = 0;
		if(tab[i] == i) nr[i] = 1;
		else nr[i] = 0;
	}
	if (ile == n) return 0;
	dl = 0; k = 1;
	for(i = 1; i <= n; i++){
		cykl.clear();
		cykl.resize(0);
		if(nr[i] == 0) {
			int pocz = i;
			nr[i] = 1;
			cykl.push_back(i);
			while(tab[pocz]!= i) {
				pocz = tab[pocz];
				nr[pocz]= 1;
				cykl.push_back(pocz);
			}
			//for(j = 0; j < cykl.size(); j++) cout <<cykl[j] <<" "; cout << endl;
			for(j = 0; j < cykl.size()/2; j++){
				wyn[k] = cykl[j];
				wyn[n + 1 - k]= cykl[cykl.size() - 1 - j];
				dl += 2;
				swap(tab[wyn[k]],tab[wyn[n +1 -k]]);
				k++;
			}			
		}
	}

		cout << endl << dl << endl;
		for(i = 1; i <= n; i++) {
			if(wyn[i] > 0) 
				cout << wyn[i] <<" ";
			}
	
	
	
	

return 0;
}