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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cmath>
using namespace std;

int n_person, heights[3001];
vector <pair<int, int>> original_heights;
vector <pair<int, int>> swaps[13];
bool swapped[3001];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n_person;
    for (int i = 1; i <= n_person; i++) {
        int a;
        cin >> a;
        original_heights.push_back({ a, i });
    }
    sort(original_heights.begin(), original_heights.end());
    for (int i = 0; i < n_person;i++)
        heights[original_heights[i].second] = i + 1;
    int n_swap = 0;
    for (int i = 0; i < 13; i++) {
        for (int j = 1; j <= n_person; j++)
            swapped[j] = 0;
        for (int a = 1; a <= n_person; a++) {
            int b = heights[a];
            if (b != a && !swapped[a] && !swapped[b]) {
                swaps[i].push_back({ a,b });
                swapped[a] = swapped[b] = 1;
                swap(heights[a], heights[b]);
            }
        }
        vector <int> unswapped;
        for (int j = 1; j <= n_person; j++)
            if (heights[j] != j && !swapped[j])
                unswapped.push_back(j);
        for (auto a : unswapped) {
            int b = heights[heights[a]];
            if (b != a && heights[heights[b]] == a && !swapped[a] && !swapped[b]) {
                swaps[i].push_back({ a,b });
                swapped[a] = swapped[b] = 1;
                swap(heights[a], heights[b]);
            }
        }
        if (swaps[i].size() == 0)
            break;
        n_swap++;
    }
    cout << n_swap << '\n';
    for (int i = 0; i < n_swap; i++) {
        cout << swaps[i].size() * 2 << '\n';
        for (int j = 0; j < swaps[i].size(); j++)
            cout << swaps[i][j].first << ' ';
        for (int j = swaps[i].size() - 1; j >= 0; j--)
            cout << swaps[i][j].second << ' ';
        cout << '\n';
    }
}