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
/* -----------------------
Autor: Tomasz Boguslawski
-------------------------- */
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<iomanip>
#include<string>
#include<sstream>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include <fstream>
#include<math.h>

#define LL long long
#define FOR(x, b, e) for(LL x = b; x <= (e); x++)
#define FORS(x, b, e, s) for(LL x = b; x <= (e); x+=s)
#define FORD(x, b, e) for(LL x = b; x >= (e); x--)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG if (debug)
#define MIN(a,b) ((a>b)?b:a)
#define MAX(a,b) ((a>b)?a:b)

using namespace std;

LL n;
LL a[4000];

bool ordered()
{
    FOR(i,1,n) if (a[i]!=i) return false;
    return true;
}

void exchange(LL i1, LL i2)
{
    LL pom=a[i1]; a[i1]=a[i2]; a[i2]=pom;
}

void doOneRound(vector<LL> &v)
{
    bool was[4000];
    LL cycle[4000];
    LL cycleLen;
    LL totalPairs=0;
    LL left[4000];
    LL right[4000];
    FOR(i,1,n) was[i]=false;
    FOR(k,1,n) if (!was[k])
    {
        // determine cycle for k:
        LL curr=k;
        was[curr]=true;
        cycle[1]=curr;
        cycleLen=1;
        while (!was[a[curr]])
        {
            cycleLen++; curr=a[curr]; cycle[cycleLen]=curr; was[curr]=true;
        }
        // cout << "Found cycle: "; FOR(i,1,cycleLen) cout << cycle[i] << " "; cout << "\n";
        LL pairCount=cycleLen/2;
        LL j1=1; LL j2=2;
        FOR(i,1,pairCount)
        {
            // cout << cycle[j1] << "-" << cycle[j2] << " ";
            exchange(cycle[j1], cycle[j2]);
            totalPairs++;
            left[totalPairs]=cycle[j1]; right[totalPairs]=cycle[j2];
            j2++; j1--; if (j1<1) j1+=cycleLen;
        }
        // cout << "\n";
    }
    FOR(i,1,totalPairs) v.push_back(left[i]); // cout << left[i] << " ";
    FORD(i,totalPairs,1) v.push_back(right[i]); //  cout << right[i] << " ";
}

/// MAIN
int main(int argc, char* argv[])
{
    // magic formula, which makes streams work faster:
	ios_base::sync_with_stdio(0);

	cin >> n;
	vector<LL> heights;
	LL h;
	FOR(i,1,n) { cin >> h; a[i]=h; heights.push_back(h); };
	sort(heights.begin(), heights.end());
	map<LL,LL> which;
	FOR(i,0,n-1) which[heights[i]]=i+1;
	FOR(i,1,n) a[i]=which[a[i]];
	// FOR(i,1,n) cout << a[i] << " "; cout << "\n";
	if (ordered()) { cout << "0\n"; return 0; };
	vector<LL> round1;
	doOneRound(round1);
	if (ordered()) {
        cout << "1\n";
        cout << round1.size() << "\n";
        FOREACH(ep,round1) cout << *ep << " ";
        cout << "\n";
        return 0;
    }
    vector<LL> round2;
    doOneRound(round2);
    cout << "2\n";
    cout << round1.size() << "\n";
    FOREACH(ep,round1) cout << *ep << " ";
    cout << "\n";
    cout << round2.size() << "\n";
    FOREACH(ep,round2) cout << *ep << " ";
    cout << "\n";
	return 0;
}