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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, K; cin >> N;
    vector<int> tab(N);
    map<int, int> mapa;
    int t = 0;
    for (auto &p : tab) { cin >> p; mapa[p]; }
    for (auto& [k, v] : mapa) {
        v = t++;
    }
    for (auto &p : tab) p = mapa[p];
    bool used[N];
    int pos[N];
    vector<vector<pii>> result;
 

    for (int x = 0; x < N; ++x) {
        vector<pii> to_swap;
        memset(used, 0, N * sizeof(bool));
        memset(pos, 0, N * sizeof(int));
        // cout << tab[x] << " ";
        for (int i = 0; i < N; ++i) {
            pos[tab[i]] = i;
            if (!used[i]) {
                if (tab[i] == i) continue;
                if (tab[tab[i]] == i) {
                    to_swap.push_back({i, tab[i]});
                    used[i] = 1;
                    used[tab[i]] = 1;
                }
            }
        }

        for (int i = 0; i < N; ++i) {
            if (tab[i] != i && !used[i] && !used[pos[i]]) {
                used[i] = 1;
                used[pos[i]] = 1;
                to_swap.push_back({i, pos[i]});
            }
        }

        for (auto p : to_swap) swap(tab[p.first], tab[p.second]);
        
        if (to_swap.size())
            result.push_back(to_swap);
        else break;
    }

    cout << result.size() << "\n";
    for (auto& to_swap : result) {
        cout << to_swap.size() * 2 << "\n";
        for (auto p : to_swap) {cout << 1 + p.first << " "; swap(tab[p.first], tab[p.second]); };
        for (int i = to_swap.size() - 1; i >= 0; --i) cout << 1 + to_swap[i].second << " ";
        cout << "\n";
    }

    return 0;
}