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
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll q=1e4+1;
ll n,t[q],d[q];
int main()
{
    cin>>n;
    for(ll i=1; i<=n; i++){
        cin>>t[i];
        d[i]=t[i];
    }
    sort(d+1,d+n+1);
    map<ll,ll> m;
    for(ll i=1; i<=n; i++){
        m.insert({d[i],i});
    }
    for(ll i=1; i<=n; i++){
        auto it=m.lower_bound(t[i]);
        t[i]=it->second;
        //cout<<t[i]<<" ";
    }
    //cout<<"\n";
    ll licz=0,j=0,k=0;
    set <ll> s;
    vector <ll> v(0),v1(0);
    
    while(s.size()!=n){
        k++;
        j=k;
        //cout<<j<<"j ";
        ll ok=0;
        while(t[j]!=j && ok==0){
            ll p; ll q=t[j];
            for(ll i=1; i<=n; i++)
                if(t[i]==j)
                    p=i;
                //cout<<q<<" "<<j<<"\n";
            if(p!=q){
                t[p]=t[q];
                t[q]=j;
                v.push_back(p);
                v1.push_back(q);
                s.insert(j); s.insert(q);
            }
            else
                ok=1;
            s.insert(j); s.insert(q); s.insert(p);
            j=p;
            //cout<<p<<" ";
        }
        s.insert(j);
        //cout<<s.size()<<"\n";
    }
    
    /*for(ll i=1; i<=n; i++)
        cout<<t[i]<<" ";
    cout<<"\n";*/
    ll a=1;
    if(!v.empty()){
        a++;
        cout<<a<<"\n"<<2*v.size()<<"\n";
        for(auto it=v.begin(); it!=v.end(); it++){
            cout<<*it<<" ";
        }
        for(auto it=v1.rbegin(); it!=v1.rend(); it++)
            cout<<*it<<" ";
        cout<<"\n";
    }
    else
        cout<<a<<"\n";
    vector <ll> v2(0),v3(0);
    set <ll> s2;
    for(ll i=1; i<=n; i++){
        auto it=s2.lower_bound(i);
        if(t[i]!=i && *it!=i){
            v2.push_back(t[i]);
            v3.push_back(i);
            s2.insert(i); s2.insert(t[i]);
        }
    }
    cout<<2*v3.size()<<"\n";
    for(auto it=v3.begin(); it!=v3.end(); it++){
            cout<<*it<<" ";
        }
    for(auto it=v2.rbegin(); it!=v2.rend(); it++)
            cout<<*it<<" ";
    return 0;
}