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

vector<pair<int, int>> odp[2];
vector<int> in;
bool u[2][3003];

int gfd[3003];

void napraw(int l, int p, int o)
{
    // for (auto i : in)
    //     cout << i << ' ';
    // cout << '\n';
    // for (int i = 0; i < in.size(); i++)
    //     cout << gfd[i] << ' ';
    // cout << "\nOCZEKUJ: " << o << " na pozycji " << p << '\n';
    if (in[p] == o)
        return;
    if (u[l][p] == 1 || u[l][gfd[o]])
        return;
    gfd[in[p]] = gfd[o];
    int nano = in[p];
    swap(in[p], in[gfd[o]]);
    u[l][p] = 1;
    u[l][gfd[o]] = 1;
    odp[l].push_back({p + 1, gfd[o] + 1});
    gfd[o] = p;
    napraw(l, nano, gfd[nano]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    in.resize(n);
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; i++)
    {
        cin >> in[i];
        p[i] = {in[i], i};
    }
    sort(p.begin(), p.end());
    for (int i = 0; i < n; i++)
    {
        in[p[i].second] = i;
        gfd[i] = p[i].second;
    }

    for (int t = 0; t < 2; t++)
    {
        for (int i = 0; i < n; i++)
        {
            napraw(t, i, i);
        }
        // cout << "---------------------------------------\n";
    }
    int ll = odp[1].size() ? 2 : 1;
    if (odp[0].size() == 0)
    {
        cout << "0\n";
        return 0;
    }
    cout << ll << '\n';
    for (int ii = 0; ii < ll; ii++)
    {
        auto i = odp[ii];
        cout << i.size() * 2 << '\n';
        for (auto j : i)
            cout << j.first << ' ';
        reverse(i.begin(), i.end());
        for (auto j : i)
            cout << j.second << ' ';
        cout << '\n';
    }
}