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

const int mxn = 1e3+3;
int tab[mxn];
int sortedtab[mxn];
int target[mxn];
int inOps[3000];

int main() {

      int n;
      scanf("%d",&n);
      for(int i = 0 ; i < n; ++i){
            scanf("%d",&tab[i]);
      }
      for(int i = 0 ; i < n; ++i){
            sortedtab[i] = tab[i];
      }
      sort(sortedtab, sortedtab+n);
      for (int i = 0; i < n; ++i) {
            target[sortedtab[i]] = i;
           // cout<<"setting target["<<sortedtab[i]<<"] to "<<i<<endl;
      }
      vector<pair<int,int>> ops;
      int res = 1;
      ops.clear();
      vector<vector<pair<int,int>>> anss;
      anss.clear();

      for(int j = 0; j < n; ++j) inOps[j] = 0;

      /*for(int i = 0 ; i < n; ++i){
           cout<<target[tab[i]]<<" ";
      }cout<<endl;*/


      bool sorted = false;
      int pass = 1;
      while(!sorted){
           // printf("pass %d\n",pass);
            for(int i = 0; i < n; ++i){
                  int t = target[tab[i]];
                  if(t != i){

                       /* for(int j = 0 ; j < n; ++j){
                              cout<<tab[j]<<" ";
                        }cout<<endl;
                        cout<<tab[i]<<" is out of target \n";*/

                        if((inOps[i] == 0) && (inOps[t] == 0)){
                              //cout<<"and the swap positions werent touched!\n";
                              ops.push_back({i,t});
                              inOps[i] = 1;
                              inOps[t] = 1;
                              swap(tab[i],tab[t]);
                              //cout<<"SWAP "<<tab[i]<<" and "<<tab[t]<<endl;
                        }else{
                              anss.push_back(ops);
                              ops.clear();
                              for(int j = 0; j < n; ++j) inOps[j] = 0;
                        }

                  }
            }

            bool fo = false;
            for(int i = 0; i < n-1; ++i){
                  if(tab[i+1] < tab[i]){
                        fo = true;
                        break;
                  }
            }
            if(!fo) sorted = true;


            ++pass;
      }

      if(!ops.empty()){
            anss.push_back(ops);
      }

      printf("%d\n",anss.size());
      for(auto& opsv : anss){
           printf("%d\n",2*opsv.size());
           for(int i = 0; i < opsv.size(); ++i){
                 printf("%d ",opsv[i].first+1);
           }
            for(int i = opsv.size() - 1; i >= 0; --i){
                  printf("%d ",opsv[i].second+1);
            }
            printf("\n");
      }

      return 0;
}