1. Abridged Problem Statement

Given an array a[1..n] (1 <= n <= 1000), you may perform steps.
In one step, you choose any number of disjoint index pairs (i, j) (no index appears in two pairs), and swap a[i] with a[j] simultaneously.

Your task: sort the array in nondecreasing order using the minimum number of steps, and output that minimum k and one valid sequence of steps (each step is listed as p i1 j1 i2 j2 ... ip jp).

---

2. Detailed editorial (how the solution works)

Key observations

1. Answer is always 0, 1, or 2 steps.
   - If the array is already sorted -> 0.
   - Sometimes it can be sorted in one parallel step (a set of disjoint swaps).
   - Otherwise it can always be done in 2 steps.

2. A "one-step sort" means:
   - There exists a set of disjoint pairs (i, j) such that after swapping those pairs, the array becomes sorted.
   - If an index is already correct (a[i] == sorted[i]), you must not move it (or you would make it incorrect unless swapped with identical value).

---

Step A: Build the sorted target

Let:
- p = original array
- q = sorted copy of p

If p == q, output 0.

---

Step B: Check if 1 step is possible (greedy pairing)

We want to transform p into q using disjoint swaps in a single step.

In one step, any moved index must be swapped with exactly one other index. Therefore, for any swap (i, j) we need:

- After swap, position i receives q[i], so we need p[j] == q[i]
- After swap, position j receives q[j], so we need p[i] == q[j]

Equivalently:
- p[i] == q[j] and p[j] == q[i]

So the algorithm:
- Maintain visited[i] indicating index already committed to a swap.
- For each index i:
  - If p[i] == q[i] or already visited, skip.
  - Search some j (not visited) that forms a 2-cycle with i w.r.t. target:
    p[i] == q[j] and p[j] == q[i].
  - If no such j exists, 1-step solution is impossible.
  - Otherwise mark i and j visited and add swap (i, j).

If this succeeds for all mismatched indices, we output 1 and these swaps.

Complexity: O(n^2) search, fine for n <= 1000.

---

Step C: Otherwise, always solve in 2 steps using permutation cycles

When 1 step is impossible, we construct a plan that always works in 2 steps.

C1) Turn the "array with duplicates" into a permutation mapping.
If all elements were distinct, sorting corresponds to applying a permutation to indices. With duplicates, we can still create a consistent permutation by distinguishing equal values by occurrence order.

Method used:
- For each value x, track how many times we've seen it so far (cnt[x]).
- In sorted array q, the block of value x starts at lower_bound(q, x).
- For p[i] = x, map it to the position:
    perm[i] = lower_bound(q, x) + cnt[x]
    cnt[x]++
Now perm is a permutation of 0..n-1 such that moving element from index i to index perm[i] will make the array match q (with stable occurrence matching).

C2) Decompose permutation into cycles.
Any permutation is a disjoint union of cycles. A 1-cycle is already correct.

- Cycle length 2: can be fixed with one swap in any step.
- Cycle length >= 3: cannot be fixed in one parallel step; but it can be fixed in two steps.

C3) Fix each cycle in two steps by making 2-cycles, then finishing.
Consider a cycle of indices: v[0] -> v[1] -> ... -> v[k-1] -> v[0] (k >= 3).

The code uses a known construction:

- In step 1: swap pairs
    (v[0], v[k-2]), (v[1], v[k-3]), ... (mirroring inward, excluding the last element v[k-1])
- In step 2: swap pairs
    (v[0], v[k-1]), (v[1], v[k-2]), ... and possibly one extra when k is odd.

Intuition:
- These swaps transform the k-cycle into disjoint 2-cycles after the first step (conceptually), which can be resolved by the second step.
- All swaps within a step are disjoint by construction (each v[t] is used at most once per step).

The implementation builds two lists turns[0] and turns[1] and outputs them.

Total steps:
- Always exactly 2 in this branch.

Complexity:
- Building permutation: O(n log n) due to lower_bound and map.
- Cycle decomposition: O(n).
- Total well within limits.

---

3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> p;

void read() {
    cin >> n;
    p.resize(n);
    cin >> p;
}

pair<bool, vector<pair<int, int>>> check_1(
    const vector<int>& p, const vector<int>& q
) {
    vector<bool> visited(p.size(), false);
    vector<pair<int, int>> swaps;

    for(int i = 0; i < (int)p.size(); i++) {
        if(visited[i] || p[i] == q[i]) {
            continue;
        }

        int found = -1;
        for(int j = 0; j < (int)p.size(); j++) {
            if(!visited[j] && p[i] == q[j] && p[j] == q[i]) {
                found = j;
                break;
            }
        }

        if(found == -1) {
            return {false, {}};
        }

        visited[i] = true;
        visited[found] = true;
        swaps.push_back({i, found});
    }

    return {true, swaps};
}

void solve() {
    // To solve this, the most important observation is that we need at most 2
    // swaps. Let's first check if the answer is 0 or 1. Checking for 0 is
    // trivial by sorting and check if equal. For 1, we can greedily assign
    // swaps - let p be the initial array, and q the target, so we can find
    // pairs (i, j) such that p[i] = q[j] and p[j] = q[i] such that every
    // position is in at most one pair.
    //
    // Now let's say we can't solve this in one turn. We start by turning p
    // into a permutation (any should work in the case of duplicates). We would
    // like in two turns to fix all cycles of this new permutation. Consider an
    // arbitrary one v[1], ..., v[k]. We want to cyclically shift it to
    // v[k], v[1], ..., v[k-1]. In the first step, we will try to make
    // independent cycles of length 2. This can be done by swapping v[1] with
    // v[k-1], then v[2] with v[k-2], and so on. This results in v[k-1] (placed
    // at index 1) and v[k] being together in a cycle, v[k-2] (placed at index
    // 2) with v[k-1] (placed at index k-1) also being together, and so on. This
    // means we can fix all these cycles in one more step. Here is an example
    // for a cycle of length 5:
    //
    //         v[1] v[2] v[3] v[4] v[5]        (1, 4) (2, 3)
    //         v[4] v[3] v[2] v[1] v[5]        (1, 5) (2, 4)
    //         v[5] v[1] v[2] v[3] v[4]

    vector<int> q = p;
    sort(q.begin(), q.end());

    if(p == q) {
        cout << 0 << endl;
        return;
    }

    auto [ok_1, swaps_1] = check_1(p, q);

    if(ok_1) {
        cout << 1 << endl;
        cout << swaps_1.size() << " ";
        for(auto [i, j]: swaps_1) {
            cout << i + 1 << " " << j + 1 << " ";
        }
        cout << endl;
        return;
    }

    vector<int> perm;
    map<int, int> cnt;
    for(int i = 0; i < n; i++) {
        int pi = lower_bound(q.begin(), q.end(), p[i]) - q.begin() + cnt[p[i]];
        cnt[p[i]]++;
        perm.push_back(pi);
    }

    vector<pair<int, int>> turns[2];
    vector<bool> visited(n, false);
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            int u = i;
            vector<int> cycle;
            while(!visited[u]) {
                cycle.push_back(u);
                visited[u] = true;
                u = perm[u];
            }

            if(cycle.size() == 1) {
                continue;
            } else if(cycle.size() == 2) {
                turns[0].push_back({cycle[0], cycle[1]});
            } else {
                int l = 0, r = (int)cycle.size() - 2;
                while(l < r) {
                    turns[0].push_back({cycle[l], cycle[r]});
                    turns[1].push_back({cycle[l], cycle[r + 1]});
                    l++;
                    r--;
                }

                if(r == l) {
                    turns[1].push_back({cycle[l], cycle[r + 1]});
                }
            }
        }
    }

    cout << 2 << endl;
    for(int t = 0; t < 2; t++) {
        cout << turns[t].size() << " ";
        for(auto [i, j]: turns[t]) {
            cout << i + 1 << " " << j + 1 << " ";
        }
        cout << endl;
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

4. Python Solution (same approach) with detailed comments

```python
import sys
from bisect import bisect_left
from collections import defaultdict

def check_one_step(p, q):
    """
    Try to transform p into q in ONE parallel step (a set of disjoint swaps).
    Returns (ok, swaps) where swaps is a list of (i, j) in 0-based indices.
    """
    n = len(p)
    used = [False] * n
    swaps = []

    for i in range(n):
        # Already fixed or already used in some swap
        if used[i] or p[i] == q[i]:
            continue

        found = -1
        # Find a partner j such that swapping i and j fixes both positions:
        # after swap, position i should become q[i], so we need p[j] == q[i]
        # after swap, position j should become q[j], so we need p[i] == q[j]
        for j in range(n):
            if not used[j] and p[i] == q[j] and p[j] == q[i]:
                found = j
                break

        if found == -1:
            return False, []

        used[i] = True
        used[found] = True
        swaps.append((i, found))

    return True, swaps


def solve():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    p = list(map(int, data[1:]))

    q = sorted(p)

    # 0 steps if already sorted
    if p == q:
        print(0)
        return

    # Try 1 step
    ok, swaps = check_one_step(p, q)
    if ok:
        print(1)
        # Output: p i1 j1 i2 j2 ...
        out = [str(len(swaps))]
        for i, j in swaps:
            out.append(str(i + 1))
            out.append(str(j + 1))
        print(" ".join(out))
        return

    # Otherwise, construct a permutation mapping with duplicate handling.
    # perm[i] = target index in q for the element currently at i
    cnt = defaultdict(int)
    perm = [0] * n
    for i, val in enumerate(p):
        base = bisect_left(q, val)    # first occurrence position of val in sorted q
        perm[i] = base + cnt[val]     # take the cnt[val]-th slot among duplicates
        cnt[val] += 1

    # Decompose perm into cycles and build two-step swap plans
    turns = [[], []]                  # turns[0] = step 1 swaps, turns[1] = step 2 swaps
    vis = [False] * n

    for i in range(n):
        if vis[i]:
            continue

        # Extract cycle starting at i
        cycle = []
        u = i
        while not vis[u]:
            vis[u] = True
            cycle.append(u)
            u = perm[u]

        k = len(cycle)
        if k == 1:
            continue
        if k == 2:
            # Fix 2-cycle in step 1
            turns[0].append((cycle[0], cycle[1]))
            continue

        # For k >= 3, use the 2-step construction from the C++ solution
        l = 0
        r = k - 2
        while l < r:
            turns[0].append((cycle[l], cycle[r]))       # step 1
            turns[1].append((cycle[l], cycle[r + 1]))   # step 2
            l += 1
            r -= 1
        if l == r:
            turns[1].append((cycle[l], cycle[r + 1]))

    # Output 2 steps
    print(2)
    for t in range(2):
        out = [str(len(turns[t]))]
        for i, j in turns[t]:
            out.append(str(i + 1))
            out.append(str(j + 1))
        print(" ".join(out))


if __name__ == "__main__":
    solve()
```

---

5. Compressed editorial

- Let q = sorted(p). If p == q, answer is 0.
- To check if 1 step is possible: every mismatched index must be paired with another index j such that swapping (i, j) makes both positions correct, i.e. p[i] == q[j] and p[j] == q[i]. Greedily find disjoint such pairs; if any i fails, 1-step is impossible.
- Otherwise answer is always 2:
  - Build a permutation perm mapping each index to its destination in q, distinguishing duplicates by occurrence count:
    perm[i] = lower_bound(q, p[i]) + occurrence_of_p[i]_so_far.
  - Decompose perm into cycles.
    - 1-cycles: ignore.
    - 2-cycles: swap in step 1.
    - k-cycles (k>=3): add swaps to step 1 and step 2 using the symmetric pairing construction:
      - step1: (v0, v{k-2}), (v1, v{k-3}), ...
      - step2: (v0, v{k-1}), (v1, v{k-2}), ... (plus one extra for odd k)
  - Output the two steps; all swaps within a step are disjoint by construction.
