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


short n, h[3000], lines;
bitset<3000> taken;
vector<short> line;
string out;


inline bool shorter(const short &i1, const short &i2)
{
    return h[i1] < h[i2];
}


int main()
{
    scanf("%hd", &n);
    for (short i = 0; i < n; ++i) scanf("%hd", h + i);

    short idxs[n];
    for (short i = 0; i < n; ++i) idxs[i] = i;
    sort(idxs, idxs + n, shorter);
    short nxt = 0;
    for (short i = 0; i < n; ++i) {
        h[idxs[i]] = nxt;
        ++nxt;
    }

    line.reserve(n % 2 == 0 ? n : n - 1);

    while (true) {
        taken.reset();
        line.clear();

        for (short i = 0; i <= n - 2; ++i)
            if (h[i] > i && !taken[i]) {
                line.emplace_back(i);
                taken[h[i]] = true;
            }

        if (line.empty()) break;

        for (short i = line.size() - 1; i >= 0; --i) {
            line.emplace_back(h[line[i]]);
            swap(h[line[i]], h[h[line[i]]]);
        }

        ++lines;
        out += to_string(line.size()) + '\n';
        for (short i = 0; i < line.size(); ++i) {
            if (i != 0) out += ' ';
            out += to_string(line[i] + 1);
        }
        out += '\n';
    }

    printf("%hd\n", lines);
    for (const char &c : out) putchar_unlocked(c);
}