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
#include <bits/stdc++.h>
using namespace std;
constexpr int maxN = 3e3+7;

int n,p[maxN],poz[maxN];
bool odw[maxN];
pair<int,int>skal[maxN];
vector<int>cykl;
vector<vector<pair<int,int>>>ans;

void dfs(int x){
    if(odw[x])
        return;
    odw[x] = true;
    cykl.push_back(x);
    dfs(p[x]);
}

void pusty(){
    ans.push_back({});
}

void essa(){
    /// ostatni musi byc na poczatku
    for(int i=(int)cykl.size()-1;i>=1;i--)
        swap(cykl[i], cykl[i-1]);
    if(ans.empty())
        pusty();
    if((int)ans.size() == 1)
        pusty();
    int l = 0, r = (int)cykl.size()-1;
    while(l < r) 
        ans[0].push_back({cykl[l++], cykl[r--]});
    l = 1, r = (int)cykl.size() - 1;
    while(l < r)
        ans[1].push_back({cykl[l++], cykl[r--]});
}

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

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>skal[i].first;
        skal[i].second = i;
    }
    sort(skal+1, skal+1+n);
    for(int i=1;i<=n;i++)
        p[skal[i].second] = i;
    for(int i=1;i<=n;i++)
        poz[p[i]] = i;

    /*
    for(int i=1;i<=n;i++)
        cout<<p[i]<<' ';
    cout<<"\n";
    */

    for(int i=1;i<=n;i++){
        if(odw[i])
            continue;
        cykl.clear();
        dfs(i);
        if((int)cykl.size() <= 1)
            continue;
        if((int)cykl.size() == 2){
            if(ans.empty())
                pusty();
            ans[0].push_back({cykl[0], cykl[1]});
            continue;
        }
        essa();
    }

    cout<<ans.size()<<"\n";
    for(auto x:ans){
        cout<<x.size() + x.size()<<"\n";
        for(pair<int,int> a:x)
            cout<<a.first<<' ';
        reverse(x.begin(), x.end());
        for(pair<int,int> a:x)
            cout<<a.second<<' ';
        cout<<"\n";
    }
}

/*

5
1670
2011
1560
1232
1447

6
1556
1449
1863
2014
1333
1220


*/