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
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n), vis(n);
	for(int &x : a) cin >> x;
	if(is_sorted(a.begin(), a.end())) {
		cout << 0 << '\n';
		return 0;
	}
	vector<int> V = a;
	vector<vector<int>> cycs;
	sort(V.begin(), V.end());
	for(int &x : a) x = lower_bound(V.begin(), V.end(), x) - V.begin();
	bool ok = true;
	for(int i = 0; i < n; i ++) if(!vis[i]) {
		vector<int> vec;		
		for(int x = i; !vis[x]; x = a[x]) vis[x] = 1, vec.emplace_back(x);
		if(vec.size() > 2) ok = false;
		cycs.push_back(vec);
	}
	if(!ok) {
		cout << 2 << '\n';
		deque<int> que;
		for(auto &vec : cycs) {
			for(int p = 1; p < (vec.size() + 1) / 2; p ++) {
				int l = vec[p], r = vec[vec.size() - p];
				swap(a[l], a[r]);
				que.emplace_front(l);
				que.emplace_back(r);
			}
		}
		cout << que.size() << '\n';
		for(int &x : que) cout << x + 1 << ' ';
		cout << '\n';
	}
	else {
		cout << 1 << '\n';
	}
	deque<int> que;
	for(int i = 0; i < n; i ++) {
		if(i < a[i]) {
			que.emplace_front(i);
			que.emplace_back(a[i]);
		}
	}
	cout << que.size() << '\n';
	for(int &x : que) cout << x + 1 << ' ';
	cout << '\n';
	return 0;
}