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

using namespace std;

void scale(vector<int>&a) {
    vector<int>b = a;
    sort(b.begin(), b.end());
    map<int, int>m;
    for(int i = 0; i < (int)a.size(); i++)
        m[b[i]] = i;
    for(int &x : a)
        x = m[x];
}

int main() {
    int n; cin >> n;
    vector<int>a(n);
    for(int &x : a)
        cin >> x;
    scale(a);
    int mx_length = 1;
    vector<vector<int>>cycles;
    vector<bool>visited(n, false);
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            cycles.emplace_back();
            for(int j = i; !visited[j]; j = a[j]) {
                cycles.back().emplace_back(j);
                visited[j] = true;
            }
            mx_length = max(mx_length, (int)cycles.back().size());
        }
    }
    if(mx_length == 1) {
        cout << "0\n";
        return 0;
    }
    
    if(mx_length == 2) {
        cout << "1\n";
        deque<int>d;
        for(vector<int>v : cycles) {
            if(v.size() == 2) {
                d.push_front(v[0]);
                d.push_back(v[1]);
            }
        }
        cout << d.size() << '\n';
        for(int x : d)
            cout << x + 1 << ' ';
        cout << '\n';
        return 0;
    }
    
    cout << "2\n";
    deque<int>d;
    for(vector<int>v : cycles) {
        int mid = ((int)v.size() - 1) / 2;
        for(int i = 1; i <= ((int)v.size() - 1) / 2; i++) {
            d.push_front(v[mid - i]);
            d.push_back(v[mid + i]);
            swap(a[v[mid - i]], a[v[mid + i]]);
        }
    }
    cout << d.size() << '\n';
    for(int x : d)
        cout << x + 1 << ' ';
    cout << '\n';
    
    mx_length = 1;
    cycles.clear();
    fill(visited.begin(), visited.end(), false);
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            cycles.emplace_back();
            for(int j = i; !visited[j]; j = a[j]) {
                cycles.back().emplace_back(j);
                visited[j] = true;
            }
            mx_length = max(mx_length, (int)cycles.back().size());
        }
    }
    
    assert(mx_length == 2);
    
    d.clear();
    for(vector<int>v : cycles) {
        if(v.size() == 2) {
            d.push_front(v[0]);
            d.push_back(v[1]);
        }
    }
    cout << d.size() << '\n';
    for(int x : d)
        cout << x + 1 << ' ';
    cout << '\n';
    return 0;
    
    return 0;
}