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
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define fi first
#define sc second
#define LL long long

vector<int> Tab;
bool solve(bool czycout){
	bool wywala = false;
	for(int i = 1; i < Tab.size(); i++){
		if(Tab[i] != i) wywala = true;
	}
	if(!wywala) return true;
	
	deque<int> Swaps;
	vector<bool> Swapped(Tab.size());
	for(int i = 1; i < Tab.size(); i++){
		if(Tab[i] != i && !Swapped[i] && !Swapped[Tab[i]]){
			Swaps.push_front(Tab[i]);
			Swaps.push_back(i);
			Swapped[Tab[i]] = true;
			Swapped[i] = true;
		}
	}
	deque<int> Swapscout; Swapscout = Swaps;
	while(!Swaps.empty()){
		Tab[Swaps.back()] = Tab[Swaps.front()];
		Tab[Swaps.front()] = Swaps.front();
		Swaps.pop_front();
		Swaps.pop_back();
	}
	
	if(czycout && !Swapscout.empty()){
		cout << Swapscout.size() << endl;
		while(!Swapscout.empty()){
			cout << Swapscout.front() << " ";
			Swapscout.pop_front();
		}
		cout << endl;
	}
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int N;
	cin >> N;
	vector<pair<int, int>> Input;
	for(int i = 0; i < N; i++){
		int a;
		cin >> a;
		Input.push_back(make_pair(a, i+1));
	}
	sort(Input.begin(), Input.end());
	vector<int> Tabs;
	Tab.resize(N+1);
	for(int i = 1; i < N+1; i++){
		Tab[Input[i-1].sc] = i;
	}
	Tabs = Tab;
	int NoT = 0;
	while(!solve(false)){
		NoT++;
	}
	cout << NoT << endl;
	Tab = Tabs;
	if(NoT != 0){ while(!solve(true)){} }
	return 0;
}