Vaihdot

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> v(n), pos(n);
    for (int i = 0; i < n; ++i)
        cin >> v[i], --v[i], pos[v[i]] = i;
    vector<pair<int, int>> swaps;
    auto do_swap = [&](int a, int b) {
        swap(v[a], v[b]);
        swap(pos[v[a]], pos[v[b]]);
        swaps.emplace_back(a, b);
    };
    for (int i = 0; i < n; ++i) {
        if (abs(pos[i] - i) == 0) continue;
        else if (abs(pos[i] - i) > 1) do_swap(pos[i], i);
        else {
            for (int j = 0; j < n && pos[i] != i; ++j) {
                if (abs(i - j) > 1 && abs(pos[i] - j) > 1) {
                    int u = pos[i];
                    do_swap(u, j);
                    do_swap(i, j);
                    do_swap(u, j);
                }
            }
            if (pos[i] != i) {
                for (int j = 0; j < n && pos[i] != i; ++j) {
                    if (abs(pos[i] - j) > 1) {
                        for (int k = j + 1; k < n && pos[i] != i; ++k) {
                            if (abs(j - k) > 1 && abs(i - k) > 1) {
                                int u = pos[i];
                                do_swap(j, u);
                                do_swap(j, k);
                                do_swap(i, k);
                                do_swap(j, k);
                                do_swap(j, u);
                            }
                        }
                    }
                }
            }
        }
    }
    if (is_sorted(v.begin(), v.end())) {
        cout << swaps.size() << '\n';
        for (auto& [l, r] : swaps) cout << l+1 << ' ' << r+1 << '\n';
    } else cout << -1 << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
}

Test 1

Subtask: 1, 2

Verdict: ACCEPTED

Test 2

Subtask: 2

Verdict: ACCEPTED