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
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdint>
#include <deque>

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<pair<int, int>> a;

    for (int i=0; i<n;i++){
        int w;
        cin>>w;
        a.push_back(make_pair(w,i));
    }

    sort(begin(a), end(a));

    vector<int> sortperm(n);
    for (int i=0; i<n;i++){
        sortperm[a[i].second]=i;

    }

    vector<uint8_t> odhaczone(n,0);

    vector<int> cykl;
    cykl.reserve(n);
    deque<int> rev1, rev2;

    for (int j=0; j<n; j++){
        if (!odhaczone[j]){//szukamy nowego cyklu
            int i=j;
            odhaczone[i]=1;
            cykl.clear();
            cykl.push_back(i);
            while (sortperm[i]!=j){
                i=sortperm[i];
                cykl.push_back(i);
                odhaczone[i]=1;
            }//permutacja w kieszeni
            int b=0, e=cykl.size()-1;
            while (b<e){
                rev1.push_front(cykl[b++]+1);
                rev1.push_back(cykl[e--]+1);
            }
            b=1, e=cykl.size()-1;
            while (b<e){
                rev2.push_front(cykl[b++]+1);
                rev2.push_back(cykl[e--]+1);
            }
        }

    }


    cout<<(!rev1.empty())+(int)(!rev2.empty())<<endl;
    if (!rev1.empty()){

        cout<<rev1.size()<<endl;
        copy (begin(rev1),end(rev1),ostream_iterator<int>(cout, " ") );
        cout<<endl;
    }
    if (!rev2.empty()){
        cout<<rev2.size()<<endl;
        copy (begin(rev2),end(rev2),ostream_iterator<int>(cout, " ") );
        cout<<endl;
    }


//    for (int i=0; i<n;i++){
//        a[i].first=a[i].second;
//        a[i].second = i;
//    }

//    sort(begin(a), end(a));



    return 0;
}