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
#include<bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
#define FOR(x, b, e) for(int x = b; x <= (e); ++x)
#define FORD(x, b, e) for(int x = b; x >= (e); --x)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ALL(c) (c).begin(), (c).end()
#define ALLD(c) (c).rbegin(), (c).rend()
#define SIZE(x) ((int)(x).size())
#define pb push_back
#define pp emplace_back
#define st first
#define nd second
#define sq(a) (a)*(a)
const int inf = 1000000001;
const double eps = 1e-9;
bool fleq(double a, double b){
	return abs(a - b) < eps;
}

int n, k;
vi a;
vi b;
vector<bool>used;
deque<int>q;
void put(int x, int y){
	if(used[y-1])return;
	used[y-1] = true;
	//printf("put %d at %d\n", x, y);
	if(a[y-1] == x)return;
	REP(i, n){
		if(a[i] == x){
			if(i != y - 1){
				q.push_front(i + 1);
				q.push_back(y);
				swap(a[i], a[y - 1]);
				put(i + 1, a[i]);
				used[i] = true;
			}
			return;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	a.resize(n);
	used.resize(n);
	b.resize(n);
	REP(i, n){
		int x;
		cin >> x;
		a[i] = b[i] = x;
	}
	sort(ALL(b));
	REP(i, n){
		REP(j, n){
			if(a[i] == b[j]){
				a[i] = j + 1;
				break;
			}
		}
	}
	if(is_sorted(ALL(a))){
		cout << 0 << '\n';
		return 0;
	}
	int start = n/2 + 1;
	put(start, start);
	FOR(i, 1, n){
		if(i == start)continue;
		put(i, i);
	}
	if(is_sorted(ALL(a))){
		cout << 1 << '\n';
		cout << q.size() << '\n';
		while(!q.empty()){
			cout << q.front() << ' ';
			q.pop_front();
		}
		return 0;
	}
	cout << 2 << '\n';
	cout << q.size() << '\n';
	while(!q.empty()){
		cout << q.front() << ' ';
		q.pop_front();
	}
	cout << '\n';
	REP(i, n){
		if(a[i] != i + 1){
			q.push_front(i + 1);
			q.push_back(a[i]);
			swap(a[a[i] - 1], a[i]);
		}
	}
	cout << q.size() << '\n';
	while(!q.empty()){
		cout << q.front() << ' ';
		q.pop_front();
	}
	return 0;
}