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
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;
pair<int,int> tab[3001];
bool odw[3001];
vector <int> koleja;
stack <int> stos;
queue<int>wyn;
int main(){
    int n;
    cin >> n;
    int maksn=0;
    int dlug=0;
    for(int i=1;i<=n;i++){
        cin >> tab[i].first;
        tab[i].second=i;
    }
    sort(tab+1,tab+n+1);
    /*for(int i=1;i<=n;i++){
        cout << tab[i].first << ' ' << tab[i].second << '\n';
    }*/
    for(int i=1;i<=n;i++){
        int j=i;
        int dlugcur=-1;
        if(tab[j].second !=j){
            while(odw[j]==0){
                    //cerr << "[prek " << j << '\n';
                odw[j]=1;
                koleja.push_back(j);
                dlug++;
                dlugcur++;
                maksn=max(maksn,dlugcur);
                j=tab[j].second;
                //cerr << " j " << j << '\n';
            }
        }
    }
    cout << min(maksn,2) << '\n';
    if(maksn==0){
        return 0;
    }
    if(maksn>1){
        int x=koleja.size()/2;
        cout << 2*x << '\n';
        for(int i=0;i<x;i++){
            cout << koleja[i] << ' ';
        }
        if(koleja.size()%2==0){
            for(int i=x;i<koleja.size();i++){
            cout << koleja[i] << ' ';
            }
        }else{
       //cerr << " X " << '\n';
            for(int i=x+1;i<koleja.size();i++){
                cout << koleja[i] << ' ';
            }
        }
        cout << '\n';
        /*for(int i=1;i<=n;i++){
        cout << tab[i].first << ' ' << tab[i].second << '\n';
    }*/


        if(koleja.size()%2==0){
            for(int i=0;i<x;i++){
                int cur=tab[koleja[i]].second;
                //tab[koleja[i]].second=tab[koleja[koleja.size()-i-1]].second;
                //tab[koleja[koleja.size()-i-1]].second=cur;
               // cout <<" tabb " << koleja[i] << " = " << tab[koleja[i]].second << '\n';
               // cout << " tab " << koleja[koleja.size()-i-1] << " = " << cur << '\n';

                int a=koleja[i];
                int b=koleja[koleja.size()-i-1];
                for(int j=0;j<=x;j++){
                    if(tab[j].second==a){
                        tab[j].second=b;
                    }else if(tab[j].second==b){
                        tab[j].second=a;
                    }
                }
                //cout <<" tabb " << koleja[i] << " = " << tab[koleja[i]].second << '\n';
                //cout << " tab " << koleja[koleja.size()-i-1] << " = " << cur << '\n';
            }
        }else{
           for(int i=0;i<x;i++){
                int cur=tab[koleja[i]].second;
                //tab[koleja[i]].second=tab[koleja[koleja.size()-i-1]].second;
                //tab[koleja[koleja.size()-i-1]].second=cur;
                //cout <<" tabb " << koleja[i] << " = " << tab[koleja[i]].second << '\n';
                //cout << " tab " << koleja[koleja.size()-i-1] << " = " << cur << '\n';

                int a=koleja[i];
                int b=koleja[koleja.size()-i-1];
                for(int j=0;j<=x;j++){
                    if(tab[j].second==a){
                        tab[j].second=b;
                    }else if(tab[j].second==b){
                        tab[j].second=a;
                    }
                }
                //cout <<" tabb " << koleja[i] << " = " << tab[koleja[i]].second << '\n';
                //cout << " tab " << koleja[koleja.size()-i-1] << " = " << cur << '\n';
            }
        }
    }
    /*for(int i=1;i<=n;i++){
        cout << tab[i].first << ' ' << tab[i].second << '\n';
    }*/

    for(int i=1;i<=n;i++){
        odw[i]=0;
    }
    int aaa=0;
    for(int i=1;i<=n;i++){
        if(odw[i]==0 && i!=tab[i].second){
            wyn.push(i);
            aaa+=2;
            stos.push(tab[i].second);
            odw[i]=1;
            odw[tab[i].second]=1;
            //cerr << " i " << i << '\n';
        }
    }
    cout << aaa << '\n';
    while(wyn.size()){
        cout << wyn.front() << ' ';
        wyn.pop();
    }
    while(stos.size()){
        cout << stos.top() << ' ';
        stos.pop();
    }
}