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
121
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int pos[100005],a[100005];
int pl[100005];
bool bi(int x,int y)
{
	return a[x]<a[y];
}
int ql[100005],qr[100005],cnt;
bool vis[100005];
int n;
void dfs(int x)
{
	vis[x]=vis[pl[x]]=true;
	if(pl[pl[x]]==x)return;
	for(int i=1;i<=n;i++)
	{
		if(pl[i]==x)
		{
			swap(pl[i],pl[pl[x]]);
			ql[++cnt]=i;
			qr[cnt]=pl[x];
			dfs(i);
			return;
		}
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),pos[i]=i;
	sort(pos+1,pos+n+1,bi);
	for(int i=1;i<=n;i++)pl[pos[i]]=i;
	bool flag0=true;
	for(int i=1;i<=n;i++)
	{
		if(pl[i]!=i)
		{
			flag0=false;
			break;
		}
	}
	if(flag0==true)
	{
		printf("0\n");
		return 0;
	}
	bool flag=true;
	for(int i=1;i<=n;i++)
	{
		if(pl[pl[i]]!=i)
		{
			flag=false;
			break;
		}
	}
	if(flag==true)
	{
		for(int i=1;i<=n;i++)
		{
			if(vis[i])continue;
			vis[i]=vis[pl[i]]=true; 
			if(pl[i]!=i)
			{
				ql[++cnt]=i;
				qr[cnt]=pl[i];
			}
		}
		printf("1\n");
		printf("%d\n",2*cnt);
		for(int i=1;i<=cnt;i++)printf("%d ",ql[i]);
		for(int i=cnt;i>=1;i--)printf("%d ",qr[i]);
		printf("\n");
		return 0;
	}
	printf("2\n");
	for(int i=1;i<=n;i++)
	{
		if(i==pl[i])
		{
			vis[i]=true;
			continue;
		}
		if(vis[i]==false)dfs(i);
	}
	printf("%d\n",2*cnt);
	for(int i=1;i<=cnt;i++)printf("%d ",ql[i]);
	for(int i=cnt;i>=1;i--)printf("%d ",qr[i]);
	printf("\n");
	cnt=0;
	for(int i=1;i<=n;i++)vis[i]=false;
	for(int i=1;i<=n;i++)
	{
		if(vis[i])continue;
		vis[i]=vis[pl[i]]=true; 
		if(pl[i]!=i)
		{
			ql[++cnt]=i;
			qr[cnt]=pl[i];
		}
	}
	printf("%d\n",2*cnt);
	for(int i=1;i<=cnt;i++)printf("%d ",ql[i]);
	for(int i=cnt;i>=1;i--)printf("%d ",qr[i]);
	return 0;
}