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
#include<bits/stdc++.h>
#define pb push_back
using namespace std;

int n;
vector<bool> vis;
vector<int> loop;
vector<pair<int, int> >h;
vector<int> sc, arr1, arr2, arr3, arr4;

void dfs(int src)
{
  loop.pb(src);
  vis[src]=1;
  if(!vis[sc[src]])dfs(sc[src]);
}

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

  cin>>n;
  sc.assign(n, 0);
  vis.assign(n, 0);
  for(int i=0;i<n;i++)
  {
    int x;
    cin>>x;
    h.pb(make_pair(x, i));
  }
  sort(h.begin(), h.end());

  for(int i=0;i<n;i++)
  {
    sc[h[i].second]=i;
  }

	bool hlp =0;
	for(int i=0;i<n;i++)
	{
		if(sc[i]!=i)hlp=1;
	}
	if(!hlp)
	{
		cout<<0;
		exit(0);
	}
	

  for(int i=0;i<n;i++)
  {
    if(!vis[i])dfs(i);
     /*  for(int i=0;i<loop.size();i++)cout<<loop[i]<<' ';
      cout<<endl;*/
    if(loop.size()>1)
    {
      for(int i=0;i<(int)(loop.size()/2);i++)
      {
        arr1.pb(loop[loop.size()-i-1]+1);
        arr3.pb(loop[i]+1);
        swap(sc[loop[i]], sc[loop[loop.size()-1-i]]);
      }
    }
    loop.clear();
  }
 hlp=0;
  for(int i=0;i<n;i++) vis[i]=0;
  for(int i=0;i<n;i++) if(sc[i]!=i)hlp=1;

  if(!hlp)
  {
    cout<<1<<endl;
    cout<<arr1.size()+arr3.size()<<endl;
    for(int i=0;i<arr1.size();i++)
    {
      cout<<arr1[i]<<' ';
    }
    for(int i=arr3.size()-1;i>=0;i--)cout<<arr3[i]<<' ';
    exit(0);
  }
  else if(hlp)
  {
    for(int i=0;i<n;i++)
    {
      if(!vis[i])dfs(i);
      if(loop.size()>1)
      {
        for(int i=0;i<=(int)(loop.size()/2)-1;i++)
        {
          arr2.pb(loop[loop.size()-i-1]+1);
          arr4.pb(loop[i]+1);
          swap(sc[loop[i]], sc[loop[loop.size()-1-i]]);
        }
      }
      loop.clear();
    }
  }

  cout<<2<<endl;
  cout<<arr1.size()+arr3.size()<<endl;
    for(int i=0;i<arr1.size();i++)
    {
      cout<<arr1[i]<<' ';
    }
    for(int i=arr3.size()-1;i>=0;i--)cout<<arr3[i]<<' ';
  cout<<endl<<arr2.size()+arr4.size()<<endl;
  for(int i=0;i<arr2.size();i++)
  {
    cout<<arr2[i]<<' ';
  }
  for(int i=arr4.size()-1;i>=0;i--)cout<<arr4[i]<<' ';
  return 0;
}