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

bool isTheSame(int n, vector<int> a, vector<int> b){
    for(int i = 0; i < n; i++)
        if(a[i] != b[i]) return false;
    return true;
}

int getIndex(vector<int> a, int val){
    vector<int>::iterator it = find(a.begin(), a.end(), val);
    return it - a.begin();
}

int main(void){
    int n, j, tmp;
    cin >> n;
    vector<int> height(n);
    vector<int> orig(n);
    vector<bool> used(n);
    vector<vector<int> > changes;
    for(int i = 0; i < n; i++) {
        cin >> height[i];
        orig[i] = height[i];
    }
    sort(height.begin(), height.end());
    while(!isTheSame(n, height, orig)){
        fill(used.begin(), used.end(), false);
        vector<int> a;
        vector<int> b;
        for(int i = 0; i < n; i++){
            if(height[i] != orig[i] && !used[i]){
                j = getIndex(height, orig[i]);
                if(used[j]) continue;
                //printf("%d is at %d but should be at %d\n", orig[i], i+1, j+1);
                used[i] = used[j] = true;
                tmp = orig[j];
                orig[j] = orig[i];
                orig[i] = tmp;
                a.insert(a.begin(), i+1);
                b.push_back(j+1);
            }
        }
        for(int i = 0; i < b.size(); i++) a.push_back(b[i]);
        //for(int i = 0; i < a.size(); i++) printf("%d ", a[i]);
        //break;
        changes.push_back(a);
        //printf("\n");
    }
    //for(int i = 0; i < n; i++) printf("%d ", orig[i]);
    //printf("\n");
    //return 0;
    n = changes.size();
    printf("%d\n", n);
    for(int i = 0; i < n; i++){
        j = changes[i].size();
        printf("%d\n", j);
        for(int k = 0; k < j; k++) printf("%d ", changes[i][k]);
        printf("\n");
    }
    return 0;
}