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
112
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <stack>
#include <queue>

using namespace std;


struct F{
	int val;
	int idx;
	F(){}
	F(int indx, int value){
		this->idx=indx;
		this->val = value;
	}
	
};

bool compare(F a, F b){
	return a.val < b.val;
}

F Ttmp[3001];
F T[3001];

bool checkIsSorted(F* tab, int n){
	for(int i = 0; i < n-1; ++i){
		if(tab[i].val >  tab[i+1].val){
			return false;
		}
	}
	return true;
}

int main(){
	int n = 0;
	cin >> n;
	for(int i = 0; i < n; ++i){
		int tmp;
		cin >> tmp;
		
		Ttmp[i] = F(i, tmp);
		T[i] = F(i, tmp);
	}
	
	bool check = checkIsSorted(T, n);
	if(check){
		cout << 1;
		cout << 1;
		cout << 1;
		return 0;
	}
	
	queue<string> result;
	int count = 0;
	
	while(!check){
		unordered_set<int> S;
		sort(Ttmp, Ttmp+n, compare);
		stack<int> K;
		queue <int> Q;
		for(int i = 0; i < n-1; ++i){
			if(S.find(i+1) == S.end() && S.find(Ttmp[i].idx+1) == S.end() && (i+1)!=(Ttmp[i].idx+1)){
				S.insert(i+1);
				S.insert(Ttmp[i].idx+1);
				Q.push(i+1);
				K.push(Ttmp[i].idx+1);
				F tmp = T[i];
				T[i] = T[Ttmp[i].idx];
				T[Ttmp[i].idx] = tmp;
			}
		}
		count++;
		result.push(to_string(Q.size()+K.size()));
		result.push("\n");
		while(!Q.empty()){
			result.push(to_string(Q.front()));
			result.push(" ");
			Q.pop();
		}
		while(!K.empty()){
			result.push(to_string(K.top()));
			result.push(" ");
			K.pop();
		}
		result.push("\n");
		check = checkIsSorted(T, n);
		//cout << "DEBUG\n";
		for(int i = 0; i < n; ++i){
			//cout << T[i].val << " idx " << T[i].idx << " | ";
			Ttmp[i].val = T[i].val;
			Ttmp[i].idx = i;
		}
		//cout << "\nDEBUG\n";
		//if(count > 10) break;
	}
	if(count > 0){
		cout << count << "\n";
		while(!result.empty()){
			cout << result.front();
			result.pop();
		}
	}else{
		cout << 0;
	}
	
	return 0;
}