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
#include<cstdio>
#include<algorithm>
#include<vector>

#define S 3007
using namespace std;

int T[S];

int P[S];
int P2[S];
vector < pair < int , int > > V;
bool vis[S];

int main(void){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n;i++){
        scanf("%d",&T[i]);
        V.push_back({T[i],i});
    }
    sort(V.begin(),V.end());
    for(int i = 0; i < V.size();i++){
        P[V[i].second] = i+1;
        P2[i+1] = V[i].second;
    }

    bool onPos = true;
    bool good = true;

    for(int i = 1; i <= n;i++){
        if(P[i] == i)
            continue;
        onPos = false;
        if(P[P[i]] != i)
            good = false;
    }
    if(onPos){
        printf("0");
        return 0;
    }
    if(good){
        printf("1\n");
        vector < int > ans;
        vector < int > ans2;
        for(int i = 1; i <= n;i++){
            if(P[i] == i)
                continue;
            if(P[i] > i){
                ans.push_back(i);
                ans2.push_back(P[i]);
            }
        }
        reverse(ans2.begin(),ans2.end());
        printf("%d\n",2*ans.size());
        for(int i = 0; i < ans.size();i++)
            printf("%d ",ans[i]);
        for(int i = 0; i < ans2.size();i++)
            printf("%d ",ans2[i]);
        return 0;
    }

    printf("2\n");
    vector < int > ans;
    vector < int > ans2;

    vector < int > ans3;
    vector < int > ans4;
    for(int i = 1; i <= n;i++){
        if(P[i] == i || vis[i] || vis[P[i]])
            continue;
        ans.push_back(i);
        ans2.push_back(P[i]);
        vis[i] = 1;
        vis[P[i]] = 1;
        swap(T[i],T[P[i]]);
        int b = P2[i];
        int w = P[P[i]];
        while(w != b && !vis[b] && !vis[w]){
            ans.push_back(b);
            ans2.push_back(w);
            //printf("%d %d*\n",b,w);
            vis[b] = 1;
            vis[w] = 1;
            swap(T[b],T[w]);
            b = P2[b];
            w = P[w];

        }
    }
    reverse(ans2.begin(),ans2.end());
    printf("%d\n",2*ans.size());
    for(int i = 0 ; i < ans.size();i++){
        printf("%d ",ans[i]);
    }
    for(int i = 0; i < ans2.size();i++){
        printf("%d ",ans2[i]);
    }
    printf("\n");
    V.clear();
    for(int i = 1; i <= n;i++){
        V.push_back({T[i],i});
        //printf("%d ",T[i]);
    }
    //printf("\n");
    sort(V.begin(),V.end());
    for(int i = 0; i < V.size();i++){
        P[V[i].second] = i+1;
        P2[i+1] = V[i].second;
    }
    ans.clear();
    ans2.clear();
    for(int i = 1; i <= n;i++){
        if(P[i] == i)
            continue;
        if(P[i] > i){
            ans.push_back(i);
            ans2.push_back(P[i]);
        }
    }
    reverse(ans2.begin(),ans2.end());
    printf("%d\n",2*ans.size());
    for(int i = 0; i < ans.size();i++)
        printf("%d ",ans[i]);
    for(int i = 0; i < ans2.size();i++)
        printf("%d ",ans2[i]);

    return 0;
}