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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<bits/stdc++.h>
using namespace std;

vector<int> sorted;
int getPosition(int x) {
    return lower_bound(sorted.begin(),sorted.end(),x)-sorted.begin();
}

int getRevPosition(int x) {
    return lower_bound(sorted.begin(),sorted.end(),x,greater<int>())-sorted.begin();
}

int main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> perm(n);
    for(auto &t:perm)
        cin >> t;
    sorted = perm;
    vector<int> cpy= perm;
    sort(sorted.begin(),sorted.end());
    vector<vector<int>> result[4];
    while(true) {
        //cout << "HERE" << endl;
        vector<int> res;
        stack<int> revRes;
        vector<bool> moved(n,false);
        for(int k=0;k<n;k++) {
            //cout << perm[k] << " ";
            if(moved[k])
                continue;
            int pos = getPosition(perm[k]);
            if(moved[pos])
                continue;
            if(pos != k) {
                res.push_back(k+1);
                revRes.push(pos+1);
                moved[k] = true;
                moved[pos] = true;
                swap(perm[k],perm[pos]);
            }
        }
        //cout <<endl;
        if(res.empty())
            break;
        while(!revRes.empty()) {
            res.push_back(revRes.top());
            revRes.pop();
        }
        result[0].push_back(res);
    }
    perm = cpy;
    while(true) {
        //cout << "MAYBE";
        vector<int> res;
        stack<int> revRes;
        vector<bool> moved(n,false);
        for(int k=n-1;k>=0;k--) {
            //cout << perm[k] << " ";
            if(moved[k])
                continue;
            int pos = getPosition(perm[k]);
            if(moved[pos])
                continue;
            if(pos != k) {
                res.push_back(k+1);
                revRes.push(pos+1);
                moved[k] = true;
                moved[pos] = true;
                swap(perm[k],perm[pos]);
            }
        }
        //cout << endl;
        if(res.empty())
            break;
        while(!revRes.empty()) {
            res.push_back(revRes.top());
            revRes.pop();
        }
        result[1].push_back(res);
    }
    if(result[1].size() < result[0].size())
        swap(result[0],result[1]);
    reverse(sorted.begin(),sorted.end());
    perm = cpy;

    while(true) {
        //cout << "OR"<<endl;
        vector<int> res;
        stack<int> revRes;
        vector<bool> moved(n,false);
        for(int k=0;k<n;k++) {
            if(moved[k])
                continue;
            int pos = getRevPosition(perm[k]);
            if(moved[pos])
                continue;
            if(pos != k) {
                res.push_back(k+1);
                revRes.push(pos+1);
                moved[k] = true;
                moved[pos] = true;
                swap(perm[k],perm[pos]);
            }
        }
        if(res.empty())
            break;
        while(!revRes.empty()) {
            res.push_back(revRes.top());
            revRes.pop();
        }
        result[2].push_back(res);
    }
    perm = cpy;
    while(true) {
        //cout << "AND"<<endl;
        vector<int> res;
        stack<int> revRes;
        vector<bool> moved(n,false);
        for(int k=n-1;k>=0;k--) {
            if(moved[k])
                continue;
            int pos = getRevPosition(perm[k]);
            if(moved[pos])
                continue;
            if(pos != k) {
                res.push_back(k+1);
                revRes.push(pos+1);
                moved[k] = true;
                moved[pos] = true;
                swap(perm[k],perm[pos]);
            }
        }
        if(res.empty())
            break;
        while(!revRes.empty()) {
            res.push_back(revRes.top());
            revRes.pop();
        }
        result[3].push_back(res);
    }
    vector<int> per(n);
    for(int k=1;k<=n;k++)
        per[k-1] = k;
    result[2].push_back(per);
    result[3].push_back(per);
    if(result[3].size() < result[2].size())
        swap(result[2],result[3]);
    if(result[2].size() < result[0].size())
        swap(result[0],result[2]);
    cout << result[0].size() <<endl;
    for(auto& t:result[0]) {
        cout << t.size() <<endl;
        for(auto &w:t)
            cout << w << " ";
        cout << endl;
    }
}