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
// Jakub Rozek
// Fotograf
// PA 2022 C r3
// czas: n*log(n)
// pami: n

#include "bits/stdc++.h"
using namespace std;

const int N=3003;

int n;
int tab[N];
int gdzie[N];
bool uzyty[N];
vector <pair<int,int>> w;

void skaluj()
{
    vector <pair<int,int>> v;
    for(int i=1; i<=n; ++i) v.push_back({tab[i],i});
    sort(v.begin(),v.end());
    int p=0;
    for(auto i:v)
    {
        ++p;
        tab[i.second]=p;    
    }
}

bool czyposortowany()
{
    for(int i=2; i<=n; ++i)
    {
        if(tab[i-1]>tab[i]) return 0;
    }
    return 1;
}

void dfs(int a, int b)
{
    b=gdzie[b];

    uzyty[a]=1;
    uzyty[b]=1;

    if(a==b) return;

    swap(tab[a],tab[b]);
    swap(gdzie[tab[a]],gdzie[tab[b]]);
    w.push_back({a,b});

    dfs(tab[b],b);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=1; i<=n; ++i) cin>>tab[i];
    skaluj();
    for(int i=1; i<=n; ++i) gdzie[tab[i]]=i;

    if(czyposortowany())
    {
        cout<<0<<"\n";
        return 0;
    }  

    for(int i=1; i<=n; ++i)
    {
        if(tab[i]==i) continue;
        if(uzyty[i]) continue;

        dfs(i,i);
    }

    if(czyposortowany())
    {
        cout<<"1\n";
        cout<<w.size()*2<<"\n";
        for(auto i:w) cout<<i.first<<" ";
        reverse(w.begin(),w.end());
        for(auto i:w) cout<<i.second<<" ";
        return 0;
    }

    cout<<"2\n";
    cout<<w.size()*2<<"\n";
    for(auto i:w) cout<<i.first<<" ";
    reverse(w.begin(),w.end());
    for(auto i:w) cout<<i.second<<" ";


    w.clear();


    for(int i=1; i<=n; ++i) uzyty[i]=0;
    for(int i=1; i<=n; ++i)
    {
        if(tab[i]==i) continue;
        if(uzyty[i]) continue;

        dfs(i,i);
    }

    cout<<"\n"<<w.size()*2<<"\n";
    for(auto i:w) cout<<i.first<<" ";
    reverse(w.begin(),w.end());
    for(auto i:w) cout<<i.second<<" ";

    return 0;
}