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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef int ll;

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

    // data input
    ll N;
    cin >> N;

    auto Tab_ = new pair<ll, ll>[N];
    for (ll i = 0; i < N; i++)
    {
        cin >> Tab_[i].first;
        Tab_[i].second = i;
    }
    sort(Tab_, Tab_ + N);
    auto Tab = new ll[N];
    for (ll i = 0; i < N; i++)
        Tab[Tab_[i].second] = i;
    delete[] Tab_;


    vector<vector<ll>> Changes;
    Changes.resize(1);
    ll R = 0;

    while (true)
    {
        Changes[R].resize(N);

        auto TabCopy = new ll[N];
        for (int i = 0; i < N; i++)
            TabCopy[i] = Tab[i];

        // try 1
        vector<ll> Changes1;
        Changes1.resize(N);
        ll c1 = 0;

        auto Used1 = new bool[N];
        for (ll i = 0; i < N; i++)
            Used1[i] = false;

        for (ll i = 0; i < N; i++)
            if (!Used1[i] && i != Tab[i] && !Used1[Tab[i]])
            {
                Used1[i] = Used1[Tab[i]] = true;
                Changes1[c1] = i;
                c1++;
                Changes1[c1] = Tab[i];
                c1++;
                swap(Tab[i], Tab[Tab[i]]);
            }
        Changes1.resize(c1);

        // try 2
        vector<ll> Changes2;
        Changes2.resize(N);
        ll c2 = 0;

        auto Used2 = new bool[N];
        for (ll i =0; i < N; i++)
            Used2[i] = false;

        for (ll i = 0; i < N; i++)
            if (!Used2[i] && i != TabCopy[i] && !Used2[TabCopy[i]])
            {
                Used2[i] = Used2[TabCopy[i]] = true;
                Changes2[c2] = i;
                c2++;
                Changes2[c2] = TabCopy[i];
                c2++;
                swap(TabCopy[i], TabCopy[TabCopy[i]]);
            }
        Changes2.resize(2);


        if (c1 || c2)
        {
            delete[] Used1;
            delete[] Used2;

            if (c1 >= c2)
            {
                Changes[R] = Changes1;
                delete[] TabCopy;
            }
            else
            {
                Changes[R] = Changes2;
                Tab = TabCopy;
                delete[] TabCopy;
            }

            R++;
            Changes.resize(Changes.size() + 1);
        }
        else
        {
            delete[] Used1;
            delete[] Used2;
            break;
        }
    }

    cout << R << "\n";
    for (int r = 0; r < R; r++)
    {
        cout << Changes[r].size() << "\n";
        for (ll i = 0; i < Changes[r].size(); i += 2)
            cout << Changes[r][i] + 1 << " ";
        for (ll i = ll(Changes[r].size() - 1); i >= 0; i -= 2)
            cout << Changes[r][i] + 1 << " ";
        cout << "\n";
    }

    return 0;
}