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
// sortujemy.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;
typedef pair<int, int> pii;
vector<pii> osoby;
vector<int> pary;
queue<int> q;
queue<vector<int>> odp;

void Rob_Pary()
{
    for (int i = 0; i < osoby.size(); i++)
    {
        pary[osoby[i].second] = i + 1;
    }
}

void Zamien(int x, int y)
{
    int poz_x, poz_y;
    poz_x = pary[x];
    poz_y = pary[y];
    pary[x] = poz_y;
    pary[y] = poz_x;
}
int Rob_Petle()
{
    int n = osoby.size();
    stack<int> kolejka;
    vector<bool> bylem(n + 1, 0);
    vector<int> p;
    vector<int> k;
    int licz = 0;
    for (int i = 1; i <= n; i++)
    {
        if (pary[i] != i)
        {
            if (!bylem[i])
            {
                kolejka.push(i);
                bylem[i] = true;
                int kolejny = pary[kolejka.top()];
                while (kolejny != i)
                {
                    bylem[kolejny] = true;
                    kolejka.push(kolejny);
                    kolejny = pary[kolejka.top()];
                }
                while (kolejka.size() > 1)
                {
                    int drugi = kolejka.top();
                    p.push_back(kolejka.top());
                    kolejka.pop();
                    k.push_back(kolejka.top());
                    int pierwszy = kolejka.top();
                    kolejka.pop();
                    Zamien(drugi, pierwszy);
                }
                while (!kolejka.empty())
                    kolejka.pop();
            }
        }
        else
        {
            licz++;
        }
    }
    q.push(p.size() * 2);
    vector<int> temp;
    for (int i = 0; i < p.size(); i++)
    {
        temp.push_back(p[i]);
    }
    for (int i = 0; i < k.size(); i++)
    {
        temp.push_back(k[k.size() - i - 1]);
    }
    odp.push(temp);
    return licz;
}
int main()
{
    int n;
    cin >> n;
    pary.resize(n + 1, 0);
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        osoby.push_back(pii(x, i + 1));
    }
    sort(osoby.begin(), osoby.end());
    Rob_Pary();
    while (Rob_Petle() != n);
    cout << q.size() - 1 << "\n";
    while (q.size()>1)
    {
        cout<<q.front()<<"\n";
        for (auto i : odp.front())
            cout << i << " ";
        cout << "\n";
        q.pop();
        odp.pop();
    }
}