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
127
128
129
130
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;



void wypisz_pare(const vector<int> &from_top, const vector<int> &from_bottom) {
    cout << from_top.size() * 2 << endl;
        
    for(int i =0; i< from_top.size(); i++)
        cout << from_top[i] << " ";
    for(int i = from_bottom.size()-1; i>=0; i--)
        cout << from_bottom[i] << " ";
    cout << endl;
}




int main()
{
    cin >> n;
    vector<pair<int,int> > wzrosty;
    for(int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        wzrosty.push_back( pair<int,int>(tmp,i) );
    }
    
    sort(wzrosty.begin(), wzrosty.end());
    
    //for(int i = 0; i < wzrosty.size(); i++)
    //    cout << wzrosty[i].first << "\t" << wzrosty[i].second << endl;
        
    
    vector< vector<int> > cycles;
    
    int max_len = 0;
        
    for(int i = 0; i < wzrosty.size(); i++) {
        if(wzrosty[i].first < 0)
            continue;
            
        vector<int> cycle;
        cycle.push_back(i);
        wzrosty[i].first = -1;
        
        while( wzrosty[ wzrosty[ cycle.back() ].second ].first >= 0 ) {
            cycle.push_back( wzrosty[ cycle.back() ].second );
            wzrosty[ cycle.back() ].first = -1;
        }
        
        if(cycle.size() > max_len)
            max_len = cycle.size();
        
        cycles.push_back(cycle);
    }
    
    /*
    for(auto it = cycles.begin(); it != cycles.end(); it++) {
        cout << it->size() << endl;
        for(auto it2 = it->begin(); it2 != it->end(); it2++)
            cout << *it2 << " ";
        cout << endl << "-------------" << endl;
    }
    */
    
    if(max_len == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    if(max_len == 2) {
        cout << 1 << endl;
        
        vector<int> from_top, from_bottom;
        
        for(auto it = cycles.begin(); it != cycles.end(); it++) {
            if(it->size() == 1)
                continue;
            from_top.push_back( (*it)[0] + 1 );
            from_bottom.push_back( (*it)[1] + 1 );
        }
        
        wypisz_pare(from_top, from_bottom);
        return 0;
    }
    
    
    vector<int> from_top1, from_bottom1;
    vector<int> from_top2, from_bottom2;
    
    for(auto it = cycles.begin(); it != cycles.end(); it++) {
        if(it->size() == 1)
            continue;
        if(it->size() == 2) {
            from_top1.push_back( (*it)[0] + 1 );
            from_bottom1.push_back( (*it)[1] + 1 );
            continue;
        }
    
        auto cycle = *it;
        for(int i=0; i < cycle.size()/2; i++) {
            from_top1.push_back( (*it)[i] + 1 );
            from_bottom1.push_back( (*it)[ cycle.size()-1-i] + 1 );
        }
        for(int i=0; i < (cycle.size()-1)/2; i++) {
            from_top2.push_back( (*it)[i] + 1 );
            from_bottom2.push_back( (*it)[ cycle.size()-2-i] + 1 );
        }
        
    }
    
    cout << 2 << endl;
    wypisz_pare(from_top1, from_bottom1);
    wypisz_pare(from_top2, from_bottom2);

    return 0;
}