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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> divide_into_cycles(const vector<pair<int,int>>& h)
{
    vector<vector<int>> cycles;
    vector<bool> checked(h.size(),false);
    for(int i=0; i<h.size(); ++i)
    {
        if(!checked[i])
        {
            int start = i;
            int pos = start;
            cycles.push_back(vector<int>());
            do
            {
                cycles[cycles.size()-1].push_back(pos);
                checked[pos] = true;
                pos = h[pos].first;
            }while(pos!=start);
        }
    }
    return cycles;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<pair<int,int>> h(n);
    for(int i=0; i<n; ++i)
    {
        h[i].first = i;
        cin >> h[i].second;
    }
    {
        vector<pair<int,int>> sorted_h(h.begin(), h.end());
        sort(sorted_h.begin(),sorted_h.end(),
            [](const pair<int,int>& a, const pair<int,int>& b){return a.second<b.second;});
        for(int i=0; i<n; ++i)
        {
            h[ sorted_h[i].first ].first = i; // invert the permutation
        }
    }
    
    vector<vector<int>> cycles = divide_into_cycles(h);

    if(cycles.size()==n)
    {
        cout << "0\n";
        return 0;
    }
    
    vector<pair<int,int>> to_flip[2];
    
    int rounds = 1;
    for(int c=0; c<cycles.size(); ++c)
    {
        if(cycles[c].size()==2)
        {
            to_flip[0].push_back(make_pair(cycles[c][0],cycles[c][1]));
        }
        else if(cycles[c].size()!=1)
        {
            for(int i=0; i<(cycles[c].size()-1)/2; ++i)
            {
                to_flip[0].push_back(make_pair( cycles[c][i], cycles[c][cycles[c].size()-2-i] ));
            }
            for(int i=0; i<cycles[c].size()/2; ++i)
            {
                to_flip[1].push_back(make_pair( cycles[c][i], cycles[c][cycles[c].size()-1-i] ));
            }
            rounds = 2;
        }
    }
    
    cout << rounds << "\n";
    for(int i=0; i<rounds; ++i)
    {
        cout << to_flip[i].size()*2 << "\n";
        for(int j=0; j<to_flip[i].size(); ++j)
        {
            cout << to_flip[i][j].first+1 << " ";
        }
        for(int j=to_flip[i].size()-1; j>=0; --j)
        {
            cout << to_flip[i][j].second+1 << " ";
        }
        cout << "\n";
    }
    
    return 0;
}