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
#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>
#include <utility>

constexpr int maxN = 3e3;

int n;
int h[maxN + 1];

std::set<int> S;
int nr;
std::unordered_map<int, int> UM;

int where[maxN + 1];
bool visited[maxN + 1];
std::vector<int> cycle;

std::vector<std::vector<std::pair<int, int>>> ans;

void DFS(int v) {
    visited[v] = true;
    cycle.push_back(v);

    if(!visited[h[v]]) {
        DFS(h[v]);
    }
}

void solve() {
    if(cycle.size() == 2) {
        if(ans.size() < 1) {
            ans.push_back({});
        }

        ans[0].push_back({cycle[0], cycle[1]});

        return;
    }

    for(int i=(int)cycle.size()-1; i>=1; i--) {
        std::swap(cycle[i - 1], cycle[i]);
    }

    while(ans.size() < 2) {
        ans.push_back({});
    }

    int l = 0;
    int r = (int)cycle.size() - 1;

    while(l < r) {
        ans[0].push_back({cycle[l], cycle[r]});

        l++;
        r--;
    }

    l = 1;
    r = (int)cycle.size() - 1;

    while(l < r) {
        ans[1].push_back({cycle[l], cycle[r]});

        l++;
        r--;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    std::cin >> n;

    for(int i=1; i<=n; i++) {
        std::cin >> h[i];
        S.insert(h[i]);
    }

    for(auto u : S) {
        UM[u] = ++nr;
    }

    for(int i=1; i<=n; i++) {
        h[i] = UM[h[i]];
        where[h[i]] = i;
    }

    for(int i=1; i<=n; i++) {
        if(!visited[i]) {
            cycle.clear();
            DFS(i);

            if(cycle.size() > 1) {
                solve();
            }
        }
    }

    std::cout << ans.size() << "\n";

    for(auto V : ans) {
        std::cout << 2 * V.size() << "\n";

        for(auto u : V) {
            std::cout << u.first << ' ';
        }

        for(int i=(int)V.size()-1; i>=0; i--) {
            std::cout << V[i].second << ' ';
        }

        std::cout << "\n";
    }
}