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

int main(){
		int n, it=0;
		scanf("%d", &n);
		set<int> s; unordered_map<int, int> mp;
		vector<int> t(n+1), j(n+1);
		for(int i = 1; i <= n; ++i){ scanf("%d", &t[i]); s.emplace(t[i]); }
		for(int i : s) mp[i] = ++it;
		for(int i = 1; i <= n; ++i) t[i] = mp[t[i]], j[t[i]] = i;
		vector<bool> used(n+1);
		vector<int> v[2], wyn[2];
		bool czy = 0;
		for(int i = 1; i <= n; ++i) if(!used[i]){
				int x = i;
				while(j[x] != t[x]){
						v[0].emplace_back(j[x]);
						v[1].emplace_back(t[x]);
						//printf("%d %d\n", j[x], t[x]);
						swap(t[j[x]], t[t[x]]);
						j[t[j[x]]] = j[x];
						j[t[t[x]]] = t[x];
						used[j[x]] = 1, used[t[x]] = 1;
						x = v[0].back();
						czy = 1;
				}
		}
		if(czy){
				for(int i : v[0]) wyn[0].emplace_back(i);
				reverse(v[1].begin(), v[1].end());
				for(int i : v[1]) wyn[0].emplace_back(i);
				v[0].clear(); v[1].clear();
		}
		
		for(int i = 1; i <= n; ++i) if(i < t[i]) v[0].emplace_back(i), v[1].emplace_back(t[i]);
		for(int i : v[0]) wyn[1].emplace_back(i);
		reverse(v[1].begin(), v[1].end());
		for(int i : v[1]) wyn[1].emplace_back(i);
		
		if(wyn[0].size() && wyn[1].size()){
				printf("2\n%d\n", (int) wyn[0].size());
				for(int i : wyn[0]) printf("%d ", i);
				printf("\n%d\n", (int) wyn[1].size());
				for(int i : wyn[1]) printf("%d ", i);
				printf("\n");
		} else if(wyn[0].size() && !wyn[1].size()){
				printf("1\n%d\n", (int) wyn[0].size());
				for(int i : wyn[0]) printf("%d ", i);
				printf("\n");
		} else if(!wyn[0].size() && wyn[1].size()){
				printf("1\n%d\n", (int) wyn[1].size());
				for(int i : wyn[1]) printf("%d ", i);
				printf("\n");
		} else printf("0\n");
		
		return 0;
}