Vaihdot

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007

using namespace std;

void test_case() {
	int n;
	cin >> n; 
    vector<int> v(n+1);

    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }

    vector<pair<int, int>> res;

    if (n == 4) {
        // brutetaan n=4
        if (v[1] == 4 && v[2] == 1 && v[3] == 2 && v[4] == 3) {
            swap(v[1], v[4]);
            res.push_back({1, 4});
        }
        if (v[1] == 3 && v[2] == 4 && v[3] == 2 && v[4] == 1) {
            swap(v[1], v[4]);
            res.push_back({1, 4});
        } else if (v[1] == 3 && v[2] == 1 && v[3] == 2 && v[4] == 4) {
            swap(v[2], v[4]);
            res.push_back({2, 4});
            swap(v[1], v[4]);
            res.push_back({1, 4});
        } else if (v[1] == 2 && v[2] == 4 && v[3] == 1 && v[4] == 3) {
            swap(v[2], v[4]);
            res.push_back({2, 4});
        } else if (v[1] == 1 && v[2] == 3 && v[3] == 2 && v[4] == 4) {
            swap(v[1], v[3]);
            res.push_back({1, 3});
        }
        if (v[1] == 1 && v[2] == 4 && v[3] == 2 && v[4] == 3) {
            res.push_back({1, 3});
            res.push_back({1, 4});
            res.push_back({1, 3});
            res.push_back({2, 4});
            cout << res.size() << "\n";

            for (auto val : res) {
                cout << val.first << " " << val.second << "\n";
            }
            return;
        } else if (v[1] == 2 && v[2] == 3 && v[3] == 1 && v[4] == 4) {
            res.push_back({2, 4});
            res.push_back({1, 4});
            res.push_back({1, 3});
            res.push_back({2, 4});

            cout << res.size() << "\n";

            for (auto val : res) {
                cout << val.first << " " << val.second << "\n";
            }
            return;
        } else if (v[1] == 4 && v[2] == 3 && v[3] == 2 && v[4] == 1) {
            res.push_back({1, 3});
            res.push_back({1, 4});
            res.push_back({2, 4});
            res.push_back({1, 4});
            res.push_back({1, 3});
            res.push_back({1, 4});

            cout << res.size() << "\n";

            for (auto val : res) {
                cout << val.first << " " << val.second << "\n";
            }
            return;
        }
    }

    
    map<int, int> where;

    for (int i = 1; i <= n; ++i) {
        where[v[i]] = i;
    }

    // locate 1 by 1
    for (int i = 1; i <= n; ++i) {
        int location = where[i];

        //cout << "at: " << i << " num is at: " << location << endl;

        if (location == i) continue;

        // helppo
        if (location - i > 1) {
            v[location] = v[i];
            where[v[i]] = location;
            v[i] = i;
            
            res.push_back({i, location});
        } else {
            // vieressä

            if (i > 2) {
                res.push_back({1, location});
                res.push_back({1, i});
                res.push_back({1, location});
                
            } else if (i < n - 2) {
                res.push_back({location, n});
                res.push_back({i, n});
                res.push_back({location, n});
            } else {
                cout << -1 << endl;
                return;
            }
            v[location] = v[i];
            where[v[i]] = location;
            v[i] = i;
        }
    }
    

    // VASTAUS
    cout << res.size() << "\n";

    for (auto val : res) {
        cout << val.first << " " << val.second << "\n";
    }
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		test_case();
		//cout << "\n";
	}

	return 0;
}


/*unsigned int sz = res.size();
    while (true) {
        for (int i = 0; i < n; ++i) {
            if (v[i] == i + 1) continue; // oikea
            int id = v[i];
            if (abs(id - i - 1) == 1) continue;
            int tg = v[id-1];
            v[id-1] = v[i];
            v[i] = tg;
            res.push_back({i+1, id});
        }
        if (sz == res.size()) break;
        sz = res.size();
    }

    if (!is_sorted(v.begin(), v.end())) {
        if (n < 4) {
            cout << -1 << "\n";
            return;
        }

        for (int i = 0; i < n-1; ++i) {
            if (v[i] == i + 1) continue;

            // Use first
            if (i >= n - 2) {
                res.push_back({1, i+1});
                res.push_back({1, i+2});
                res.push_back({1, i+1});
                v[i] = i + 1;
                v[i + 1] = i + 2;
            } else { // use last
                res.push_back({i+1, n});
                res.push_back({i+2, n});
                res.push_back({i+1, n});
                v[i] = i + 1;
                v[i + 1] = i + 2;
            }
        }
    }*/

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED