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

typedef pair<int, int> PII;

constexpr int M = 3007;

int n;
int h[M], idx[M];
bool marked[M];

PII sh[M];

deque<int> p1, p2;
queue<int> Q;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	
	for(int i=1; i<=n; i++){
		cin >> h[i];
		sh[i].first = h[i];
		sh[i].second = i;
	}
	
	sort(sh+1, sh+n+1);
	
	for(int i=1; i<=n; i++){
		h[sh[i].second] = i;
		idx[i] = sh[i].second;
	}
	
	for(int i=1; i<=n; i++){
		if(h[i] == i || marked[i]) continue;
		Q.push(i);
		while(!Q.empty()){
			int act = Q.front();
			Q.pop();

			if(h[h[act]] == act){
				p2.push_front(act);
				p2.push_back(h[act]);
				marked[act] = 1;
				marked[h[act]] = 1;
				continue;
			}		
			else{
				int f = idx[act]; 
				idx[h[act]] = f;
				
				p1.push_front(h[act]);
				p1.push_back(f);
				
				swap(h[h[act]], h[f]);
				
				p2.push_front(act);
				p2.push_back(h[act]);
				
				marked[act] = 1;
				marked[h[act]] = 1;
				
				if(h[h[act]] == act) break;
				
				Q.push(f);
			}
		}
	}	
	
	if(p1.size()){
		cout << "2\n";
		cout << p1.size() << '\n';
		for(auto i : p1) cout << i << ' ';
		cout << '\n';
		cout << p2.size() << '\n';
		for(auto i : p2) cout << i << ' ';
		cout << '\n';
	}
	else if(p2.size()){
		cout << 1 << '\n';
		cout << p2.size() << '\n';
		for(auto i : p2) cout << i << ' ';
		cout << '\n';
	}
	else cout << 0 << '\n';
		
	return 0;
}