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
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector> 
using namespace std;
typedef long long ll;
typedef long double ld;
#define st first
#define nd second

vector<pair<int, int>> r1, r2;



void add(vector<int> &cycle)
{
    int k = cycle.size();
    // for (int x: cycle) cout << x << ' ';
    if (k == 1) return;
    if (k == 2) 
    {
        r1.push_back({cycle[0], cycle[1]});
        return;
    }
    if (k&1)
    {
        int mid = k/2;
        for (int i = 1; i <= k/2; i++) r1.push_back({cycle[mid-i], cycle[mid+i]});
        for (int i = 1; i <= k/2; i++) r2.push_back({cycle[i], cycle[k-i]});
    }
    else
    {
        int mid = k/2;
        for (int i = 1; i < k/2; i++) r1.push_back({cycle[mid-i], cycle[mid+i]});
        r2.push_back({cycle[0], cycle[1]});
        for (int i = mid, j = mid+1; i > 1; i--, j++) r2.push_back({cycle[i], cycle[j]});
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<int> h(n);
    vector<int> nh(3001);
    for (int i = 0; i < n; i++) 
    {
        cin >> h[i];
        nh[h[i]] = 1;

    }
    int l = 0;
    for (int i = 1; i <= 3000; i++)
    {
        if (nh[i]) nh[i] = l++;
    }
    for (int i = 0; i < n; i++) h[i] = nh[h[i]];
    // for (int x: h) cout << x << ' ';
    vector<bool> vis(n);
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            vector<int> cycle;
            cycle.push_back(i);
            int u = h[i];
            while (u != i)
            {
                vis[u] = true;
                cycle.push_back(u);
                u = h[u];
            }
            add(cycle);
        }
    }
    if (r1.empty())
    {
        cout << 0;
        return 0;
    }
    if (r2.empty()) cout << "1\n";
    else cout << "2\n";
    cout << r1.size()*2 << '\n';
    for (int i = 0; i < r1.size(); i++) cout << r1[i].st+1 << ' ';
    for (int i = r1.size()-1; i >= 0; i--) cout << r1[i].nd+1 << ' ';
    cout << '\n';
    if (r2.empty()) return 0;
    cout << r2.size()*2 << '\n';
    for (int i = 0; i < r2.size(); i++) cout << r2[i].st+1 << ' ';
    for (int i = r2.size()-1; i >= 0; i--) cout << r2[i].nd+1 << ' ';


    
}