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
#include <bits/stdc++.h>

int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(NULL);
    int n;
    std::cin >> n;
    std::vector<int> v(n, 0);
    for (auto &x : v) std::cin >> x;

    std::vector<int> w = v;
    std::sort(w.begin(), w.end());
    std::map<int, int> map;
    for (int i = 0; i < w.size(); i++) map[w[i]] = i;
    for (auto &x : v) x = map[x];

    std::vector<int> A, B, C, D;

    // first round
    w = v;
    for (int i = 0; i < n; i++) {
        if (v[i] != -1) {
            std::vector<int> c = {i};
            std::vector<int> d;
            int j = v[i];
            v[i] = -1;
            while (j != i) {
                c.push_back(j);
                int next = v[j];
                v[j] = -1;
                j = next;
            }

            for (int j = 0; j < c.size()/2; j++) {
                A.push_back(c[j]);
                B.push_back(c[c.size()-1-j]);
                std::swap(w[A.back()], w[B.back()]);
            }
        }
    }

    // second
    for (int i = 0; i < w.size(); i++) {
        if (w[i] < i) {
            C.push_back(i);
            D.push_back(w[i]);
        }
    }

    if (A.empty()) {
        std::cout << "0\n";
    } else if (C.empty()) {
        std::cout << "1\n" << A.size() + B.size() << "\n";
        for (auto x : A) std::cout << x+1 << " ";
        std::reverse(B.begin(), B.end());
        for (auto x : B) std::cout << x+1 << " ";
        std::cout << "\n";
    } else {
        std::cout << "2\n";
        std::cout << A.size() + B.size() << "\n";
        for (auto x : A) std::cout << x+1 << " ";
        std::reverse(B.begin(), B.end());
        for (auto x : B) std::cout << x+1 << " ";
        std::cout << "\n";

        std::cout << C.size() + D.size() << "\n";
        for (auto x : C) std::cout << x+1 << " ";
        std::reverse(D.begin(), D.end());
        for (auto x : D) std::cout << x+1 << " ";
        std::cout << "\n";
    }
}