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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <numeric>

std::vector<size_t> change(std::vector<size_t> &s)
{
    std::vector<bool> alreadyMoved(s.size(), false);
    std::vector<size_t> m;
    std::vector<size_t> n;
    for(size_t i =0; i<s.size(); ++i)
    {
        size_t i2 = s[i];
        if(not alreadyMoved[i] and not alreadyMoved[i2] and i2 != i) 
        {
            m.push_back(i);
            n.push_back(i2);
            alreadyMoved[i]=true; alreadyMoved[i2]=true;
            std::iter_swap(s.begin()+i, s.begin()+i2);
        }
    }

    for(size_t x = 0; x <n.size(); ++x)
    {
       m.push_back(*(n.cend()-1-x));
    }
    return m;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    int n;
    std::cin>>n;
    std::vector<int> students;
    students.reserve(n);
    for(int i=0;i<n;++i)
    {
        int h; std::cin>>h;
        students.push_back(h);
    }

    std::vector<size_t> pos(students.size());
    std::iota(pos.begin(), pos.end(), 0);
    std::stable_sort(pos.begin(), pos.end(),
       [&students](size_t i1, size_t i2) {return students[i1] < students[i2];});
    std::vector<size_t> pox(students.size());
    for(size_t i =0; i< pos.size();++i){ pox[pos[i]] = i;}

    bool oneMore = true;
    std::vector<std::vector<size_t>> result;
    while(oneMore)
    {
    auto x = change(pox);
    if (x.empty()) { oneMore = false;}
    else result.push_back(x);
    }
    std::cout<< result.size()<<std::endl;
    for(const auto& r:result)
    {
    std::cout<< r.size()<<std::endl;
        for(const auto& p:r){ std::cout<<(p+1)<<" ";}
        std::cout<<std::endl;
    }
    return 0;
}