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

using namespace std;

constexpr int MAXN=3e3+7;
int tab[MAXN], odw[MAXN];
pair <int, int> tab2[MAXN];
vector <pair <int, int> > wynik[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;

    cin >> n;

    for (int i=1; i <= n; i++) {
        cin >> tab[i];
        tab2[i] = {tab[i], i};
    }

    sort(tab2+1, tab2+n+1);

    for (int i=1; i <= n; i++) {
        tab[tab2[i].second] = i;
        odw[i] = tab2[i].second;
    }

    int pozycja=1, linia=1, ile;
    set <int> wys;
    bool posortowane=0;

    for (linia; !posortowane; linia++) {
        posortowane = 1;
        ile = 0;
        wys.clear();

        for (int i=1; i <= n && ile <= n/2; i++) {
            if (tab[i] != i) {
                posortowane = 0;

                if (wys.count(i) || wys.count(tab[i]))
                    continue;

                wys.insert(i);
                wys.insert(tab[i]);
                
                wynik[linia].push_back({i, odw[i]});
                tab[odw[i]] = tab[i];
                odw[tab[i]] = odw[i];

                tab[i] = i;
                odw[i] = i;

                ile++;
            }
        }
    }

    linia -= 2;

    cout << linia << '\n';

    for (int i=1; i <= linia; i++) {
        cout << 2 * wynik[i].size() << '\n';

        for (int j=0; j < wynik[i].size(); j++)
            cout << wynik[i][j].first << ' ';

        for (int j=wynik[i].size()-1; j >= 0; j--)
            cout << wynik[i][j].second << ' ';

        cout << '\n';
    }

    return 0;
}