реши задачу: Леша решил отсортировать перестановк...

Ниже ‒ полное раз-​реше­ние задачи (идея, коррект­ность, асимпто­тика) + реа­ли­зация на C++17, которая выводит конк­рет­ную после­до­ва­тель­ность ≤ 4 n обменов.

---

1. Операция «пере­ставить 1»

Пусть pos1 – теку­щий индекс, в котором лежит 1.

text
move1(t)      //  переместить 1 в позицию t   ( ≤ 2 хода )
┌ если |pos1–t| ≤ n/2:          swap(pos1 , t)
│ иначе
│ ├ if pos1 < t : mid = pos1 + n/2      // mid ∈ (pos1 , t]
│ └ if pos1 > t : mid = pos1 – n/2      // mid ∈ [t , pos1)
│   swap(pos1 , mid)        // |pos1–mid| = n/2
│   swap(mid , t)           // |mid – t| ≤ n/2
└► pos1 = t .

Доказательство: во 2-м случае mid находится между обоими концами ровно на n/2, следо­ва­тельно обе замены разрешены. Всего ≤ 2 операции.

---

2. Как поставить число x на своё место x

Пусть
idx – номер, в котором сейчас лежит x (ищем в массиве p).

Лёгкая половина |idx – x| ≤ n/2

1. move1(x) // ≤ 2
2. swap(x , idx) // ≤ 1

Итого ≤ 3 операций.

Тяжёлая половина |idx – x| > n/2

Тогда позиции idx и x лежат в раз­ных пола­винах массива.

1. move1(idx) // ≤ 2 (встали на число x)
2. swap(idx , x) // ≤ 1 (1 ушла в другую полу­вину, // а x пришёл в “чужую” полу­вину)
3. move1(x) // ≤ 2 (возвращаем 1 назад через // ту же сере­дину)

Максимум 4 обмена.

---

3. Весь алгоритм

text
for v = 1 … n:
    while p[v] ≠ v:
        idx = позиция(v)
        if |idx - v| ≤ n/2:
            // лёгкий случай
            move1(v)          // ≤ 2
            swap(v , idx)     //  1
        else:
            // тяжёлый случай
            move1(idx)        // ≤ 2
            swap(idx , v)     //  1
            move1(v)          // ≤ 2

Счёт операций

• лёгкий случай ≤ 3, тяжёлый ≤ 4.
  Каждое число исправляется ровно один раз ⇒
  Σ operations ≤ 4 · (n – 1) ≤ 4 n.

---

4. Корректность

Инвариант: перед началом итерации v все элементы 1…v-1 уже стоят на своих местах, а значение p остаётся перестановкой.

Док‐во делается по индукции, используя то, что все обмены разрешены (расстояние не превышает n/2, а всегда уча­ствует индекс, где лежит 1) и что после завер­шения блока «ставим v» в позиции v стоит именно v.

---

5. Случай n = 3

При n = 3 един­ствен­ные недости­жимые переста­новки – те, где 1 стоит посередине и вокруг неё обрат­ный порядок, то есть [3, 1, 2] и [3, 2, 1]. Все прочие сортиру­ются описан­ным методом (в лек­гой версии алгоритм делает ровно 3 хода).

---

6. Сложность

Время O(n) — ищем текущие позиции с обрат­ным массивом pos[].
Память O(n).
Число операций ≤ 4 n, как и требуется.

---

7. Реализация (C++17)

cpp
#include <bits/stdc++.h>
using namespace std;

struct Op {int i, j;};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;  cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> p(n+1), pos(n+1);
        for (int i = 1; i <= n; ++i) {
            cin >> p[i];
            pos[p[i]] = i;
        }

        auto do_swap = [&](int a, int b, vector<Op>& ans) {
            swap(p[a], p[b]);
            pos[p[a]] = a;
            pos[p[b]] = b;
            ans.push_back({a, b});
        };

        auto move1 = [&](int to, vector<Op>& ans) {
            while (pos[1] != to) {
                int cur = pos[1];
                if (abs(cur - to) <= n/2) {
                    do_swap(cur, to, ans);
                } else if (cur < to) {
                    int mid = cur + n/2;
                    do_swap(cur, mid, ans);
                } else {
                    int mid = cur - n/2;
                    do_swap(cur, mid, ans);
                }
            }
        };

        vector<Op> ans;
        bool bad = (n == 3) &&
                   ((p[2] == 1 && p[1] == 3) || (p == vector<int>{0,3,2,1}));

        if (bad) { cout << -1 << '\n'; continue; }

        for (int v = 1; v <= n; ++v) {
            while (p[v] != v) {
                int idx = pos[v];
                if (abs(idx - v) <= n/2) {          // лёгкий
                    move1(v, ans);
                    do_swap(v, idx, ans);
                } else {                            // тяжёлый
                    move1(idx, ans);
                    do_swap(idx, v, ans);
                    move1(v, ans);
                }
            }
        }

        cout << ans.size() << '\n';
        for (auto [i,j] : ans) cout << i << ' ' << j << '\n';
    }
    return 0;
}

Длина списка ans никогда превышает 4 n, а каждая выведенная пара удовлетворяет условиям задачи.