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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define maxn 3005
using namespace std;

pair <int, int> wej[maxn];
int a[maxn];
int b[maxn];
int gdzie[maxn];

void napraw(int pos)
{
	int wart = b[pos];
	
	if(b[wart])
	{
		if(b[wart] != pos)
		{
			cout << "dupa\n";
			exit(1);
		}
	}
	else
	{
		b[wart] = pos;
		napraw(wart);
	}
	
	if(!b[gdzie[wart]])
	{
		b[gdzie[wart]] = a[pos];
		napraw(gdzie[wart]);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		cin >> wej[i].first;
		wej[i].second = i;
	}
	sort(wej+1, wej+1+n);
	for(int i = 1; i <= n; ++i) a[wej[i].second] = i;
	
	//for(int i = 1; i <= n; ++i) cout << a[i] << " ";
	//cout << "\n";
	
	bool czy0 = 1;
	for(int i = 1; i <= n; ++i) if(a[i] != i) czy0 = 0;
	if(czy0)
	{
		cout << 0;
		return 0;
	}
	
	for(int i = 1; i <= n; ++i) gdzie[a[i]] = i;
	
	bool czy1 = 1;
	for(int i = 1; i <= n; ++i) if(gdzie[i] != a[i]) czy1 = 0;
	if(czy1)
	{
		cout << 1 << "\n";
		vector <int> t;
		for(int i = 1; i <= n; ++i) if(a[i] < i) t.emplace_back(i);
		for(int i = n; i >= 1; --i) if(a[i] < i) t.emplace_back(a[i]);
		cout << t.size() << "\n";
		for(int i : t) cout << i << " ";
		cout << "\n";
		return 0;
	}
	
	for(int i = 1; i <= n; ++i)
	{
		if(!b[i])
		{
			b[i] = a[i];
			napraw(i);
		}
	}
	
	/*cout << "b: ";
	for(int i = 1; i <= n; ++i) cout << b[i] << " ";
	cout << "\n";*/
	
	cout << 2 << "\n";
	
	vector <int> t1, t2;
	for(int i = 1; i <= n; ++i) if(i < gdzie[b[i]])
	{
		t1.emplace_back(i);
		t2.emplace_back(gdzie[b[i]]);
	}
	for(int i = t2.size()-1; ~i; --i) t1.emplace_back(t2[i]);
	cout << t1.size() << "\n";
	for(int i : t1) cout << i << " ";
	cout << "\n";
	
	vector <int> t;
	for(int i = 1; i <= n; ++i) if(b[i] < i) t.emplace_back(i);
	for(int i = n; i >= 1; --i) if(b[i] < i) t.emplace_back(b[i]);
	cout << t.size() << "\n";
	for(int i : t) cout << i << " ";
	cout << "\n";
	
	return 0;
}