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

#define int int64_t
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int M[3009];
int tab[3009];
bool vis[3009];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	vector<int> tmp;
	for(int i=0;i<n;i++) {
		cin >> tab[i];
		tmp.pb(tab[i]);
	}
	sort(all(tmp));
	for(int i=0;i<n;i++) M[tmp[i]] = i;
	for(int i=0;i<n;i++) tab[i] = M[tab[i]];

	vector<deque<int>> ans(2);

	for(int i=0;i<n;i++) {
		if(!vis[i]) {
			vis[i] = true;
			vector<int> v = {i};
			int I = tab[i];
			while(I != i) {
				vis[I] = true;
				v.pb(I);
				I = tab[I];
			}
			if(sz(v) == 1) continue;
			if(sz(v) == 2) {
				ans[1].pb(v[0]);
				ans[1].push_front(v[1]);
				continue;
			} 
			for(int j=0;j<(sz(v)+1)/2-1;j++) {
				ans[0].pb(v[j+1]);
				ans[0].push_front(v[sz(v)-j-1]);
				swap(tab[v[j+1]], tab[v[sz(v)-j-1]]);
			}
			ans[1].pb(v[0]);
			ans[1].push_front(v[1]);
			for(int j=2;j<sz(v)/2+1;j++) {
				ans[1].pb(v[j]);
				ans[1].push_front(v[sz(v)-j+1]);
			}
		}
	}
	if(sz(ans[0])==0 and sz(ans[1])==0) {
		cout << "0\n";
		return 0;
	}
	if(sz(ans[0])==0) {
		cout << "1\n";
		cout << sz(ans[1]) << "\n";
		for(int x:ans[1]) cout << x+1 << " ";
		cout << "\n";
		return 0;
	}
	cout << "2\n";
	cout << sz(ans[0]) << "\n";
	for(int x:ans[0]) cout << x+1 << " ";
	cout << "\n";
	cout << sz(ans[1]) << "\n";
	for(int x:ans[1]) cout << x+1 << " ";
	cout << "\n";

}