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
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
void compress(int a[], int n)
{
    int ind[3007];
    for(int i=0;i<3007;i++)
        ind[i]=-1;
    for(int i=0;i<n;i++)
        ind[a[i]]=i;
    int j=0;
    for(int i=0;i<3007;i++)
    {
        if(ind[i]!=-1)
        {
            a[ind[i]]=j;
            j++;
        }
    }
    return;

}
bool sorted(int a[], int n)
{
    for(int i=1;i<n;i++)
    {
        if(a[i-1]>a[i])
            return 0;
    }
    return 1;
}
bool mate_in_one(int a[], int n, bool wypisz)
{
    for(int i=0;i<n;i++)
    {
        if(a[a[i]] != i)
            return 0;
    }
    if(wypisz)
        cout<<"1\n";
    deque<int> kol;
    int b[n];
    for(int i=0;i<n;i++)
        b[i]=0;
    for(int i=0;i<n;i++)
    {
        if(b[i]==0 && b[a[i]]==0 && i!=a[i])
        {
            kol.push_front(a[i]);
            kol.push_back(i);
            b[i]=1;
            b[a[i]]=1;
        }
    }
    cout<<kol.size()<<"\n";
    while(!kol.empty())
    {
        cout<<kol.front()+1<<" ";
        kol.pop_front();
    }
    return 1;
}
void reverse_cycle(int a[], int n)
{
    int b[n];
    for(int i=0;i<n;i++)
        b[i]=0;
    int k;
    vector<int> v;
    deque<int> kol;
    for(int i=0;i<n;i++)
    {
        v.clear();
        k=i;
        while(b[k]==0)
        {
            b[k]=1;
            v.push_back(k);
            k=a[k];
        }
        for(int j=0;j<v.size()/2;j++)
        {
            kol.push_front(v[j]);
            kol.push_back(v[v.size()-j-1]);
            swap(a[kol.front()],a[kol.back()]);
        }
    }
    cout<<kol.size()<<"\n";
    while(!kol.empty())
    {
        cout<<kol.front()+1<<" ";
        kol.pop_front();
    }
    cout<<"\n";
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    if(sorted(a,n))
    {
        cout<<"0\n";
        return 0;
    }
    compress(a,n);
    if(mate_in_one(a,n,1))
        return 0;
    cout<<"2\n";
    reverse_cycle(a,n);
    mate_in_one(a,n,0);
}