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
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

namespace {
    using std::cin;
    using std::cout;
    using heights_t = std::vector<size_t>;
    using conv_map_t = std::map<size_t, size_t>;
    using std::is_sorted;
    using std::swap;
    using results_t = std::vector<std::vector<size_t>>;

    void build_conv_maps(
        heights_t const & heights, heights_t::iterator it_right_sorted,
        conv_map_t & i_h_map, conv_map_t & h_i_map
    ) {
        if (!i_h_map.empty()) i_h_map.clear();
        if (!h_i_map.empty()) h_i_map.clear();
        size_t k = 1;
        for (auto it = heights.begin(); it != it_right_sorted; ++it) {
            i_h_map[k] = *it;
            h_i_map[*it] = k;
            ++k;
        }
    }
}

int main() {
    size_t n, height;
    heights_t heights = {};
    conv_map_t i_h_map, h_i_map, final_order_map;
    results_t results;

    cin >> n;
    for (size_t k = 0; k < n; ++k) {
        cin >> height;
        heights.push_back(height);
        final_order_map[height] = 0;
    }
    while (!is_sorted(heights.begin(), heights.end())) {
        build_conv_maps(
            heights, heights.end(),
            i_h_map, h_i_map
        );

        results.push_back({});

        while (!i_h_map.empty() && !h_i_map.empty()) {
            if (i_h_map.rbegin()->second != h_i_map.rbegin()->first) {

                auto x = i_h_map.rbegin()->first;
                auto y = h_i_map.rbegin()->second;
                auto it_final_1 = final_order_map.begin();
                auto it_final_2 = it_final_1;
                for (size_t k = 1; k < x; ++k)
                    ++it_final_1;
                for (size_t k = 1; k < y; ++k)
                    ++it_final_2;
                if (it_final_1->first == h_i_map.rbegin()->first
                    || it_final_2->first == i_h_map.rbegin()->second) {

                if (x > y) swap(x, y);
                results.back().push_back(x);
                results.back().push_back(y);

                swap(
                    heights[x - 1],
                    heights[y - 1]
                );

                }

                h_i_map.erase(heights[x - 1]);
                h_i_map.erase(heights[y - 1]);
                i_h_map.erase(x);
                i_h_map.erase(y);

            } else {
                i_h_map.erase(i_h_map.rbegin()->first);
                h_i_map.erase(h_i_map.rbegin()->first);
            }
        }
    }

    cout << results.size() << '\n';
    for (auto const & round : results) {
        cout << round.size() << '\n';
        for (size_t k = 0; k < round.size(); k += 2)
            cout << round[k] << ' ';
        for (size_t k = round.size(); k > 0; k -= 2)
            cout << round[k - 1] << ' ';
        cout << '\n';
    }

    return 0;
}