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
#include<vector>
#include <iostream>
#include<algorithm>
#include<queue>
#include<bitset>
using namespace std;
typedef long long ll;
#define f first
#define s second
int n;
int A[5000],poz[5000],id[5000],B[5000];
deque<int> odp[5000];
int main()
{ ios_base::sync_with_stdio(); cin.tie();
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
        B[i]=A[i];
    }
    sort(B,B+n);
    for(int i=0;i<n;i++)id[B[i]]=i;
    for(int i=0;i<n;i++){A[i]=id[A[i]]; poz[A[i]]=i;}
    int licz=0;
    bitset<5000> curr;
    int left=n;
    for(int i=0;i<n;i++)if(A[i]==i)left--;
    while(1)
    {   int l=0;
        bool end=1;
        for(int i=0;i<n;i++)
        {
            if(curr[i])continue;
            if(A[i]==poz[i]&&A[i]!=i&&curr[poz[i]]==0)
            {   end=0;
                odp[licz].push_back(i);
                odp[licz].push_front(A[i]);
                A[A[i]]=A[i];
                A[i]=i;
                left-=2;
            }
          if(A[i]!=i)
          { end=0;
              int a=i,b=poz[i];
              int a2=a,b2=b;
              while(l<left-left%2&&curr[a]==0&&curr[b]==0&&a!=b)
              { curr[a]=1;
                  curr[b]=1;
                  odp[licz].push_front(a);
                  odp[licz].push_back(b);
                      swap(A[a],A[b]);
                  a=A[b];
                  b=poz[b];
                  
                  swap(poz[A[a2]],poz[A[b2]]);
                  a2=a; b2=b;
                  l+=2;
         //6         for(int i=0;i<n;i++)cout<<A[i]+1<<' '; cout<<endl;
              }
          }
                
            }
            
        
        if(end||licz>3)break;
        else licz++;
        curr^=curr;
        
    }
    cout<<licz<<endl;
    for(int i=0;i<licz;i++)
    {
        cout<<odp[i].size()<<endl;
        for(int k : odp[i])cout<<k+1<<' '; cout<<endl;
    }
    
    
    return 0;
}