<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

539. Multiswap Sorting
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

You are employed to implement a new fast sorting algorithm called multiswap sorting. The basic idea is simultaneous execution of multiple parallel swaps. You are given an array containing n integer elements a1, a2,..., an. At each step of the algorithm you must select one or more nonintersecting pairs of elements and swap the elements in each of the selected pairs.

For example, you are given the array [5, 4, 3, 2, 1]. At one step you can select two pairs (5, 1) and (4, 2), swap elements in them and get the array 1, 2, 3, 4, 5. Pairs (1, 2) and (2, 3) cannot be selected at one step, because they have the common element 2. So it is possible to sort the array [5, 4, 3, 2, 1] in one step.

Sort the given array in the minimum possible number of steps carrying out selection of pairs at each step optimally. Note that you are not required to minimize the total number of single swaps but the number of steps.

Input
The first line contains an integer n (1 ≤ n ≤ 1000) — the number of elements in the array. In the second line the elements ai are given. The numbers ai are integers not exceeding 109 by absolute value.

Output
In the first line output the minimum number of steps k. The next k lines should describe multiswaps in the form "p i1 j1 i2 j2 ip jp", where p > 0 is a number of pairs selected at the current step, is js are the indices of elements in the s-th pair (is ≠ js, indices of elements in distinct pairs must be distinct). The elements are indexed by integers from 1 to n according to their positions in the array at the current step. The order of pairs and the order of elements in pairs are unimportant. If there are multiple solutions with the minimum number of steps, output any.

Example(s)
sample input
sample output
3
1 2 3
0

sample input
sample output
5
5 4 3 2 1
1
2 1 5 2 4

sample input
sample output
4
3 1 2 2
2
2 1 2 3 4
1 4 2



Note
In the last example, after the first step the array takes the form 1, 3, 2, 2. At the second step 3 is swapped with the last 2. Note that the swap of the 3-rd and the 4-th elements at the first step does not change the array (these elements are equal). However, the answer with this pointless swap, as well as without it, is optimal, because your goal is to minimize the number of steps but not the number of swaps.

<|response|>
1. Abridged problem statement

Given an integer array a[1..n] (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 the elements in each pair simultaneously.

Goal: sort the array nondecreasingly using the minimum number of steps, and output that minimum k and one optimal sequence of steps.

---

2. Key observations

1. The minimum number of steps is always 0, 1, or 2.
   - 0 if already sorted.
   - Sometimes sorting can be done in 1 parallel step by choosing the right disjoint swaps.
   - Otherwise it can always be done in 2 steps.

2. Characterization of a 1-step solution.
   Let p be the current array and q = sorted(p) be the target.
   In one step, every index that changes must be swapped with exactly one partner.
   For a swap (i, j) to make both positions correct immediately, we need:
   - after swap p[i] goes to position j, so p[i] == q[j]
   - after swap p[j] goes to position i, so p[j] == q[i]

   i.e. p[i] == q[j] and p[j] == q[i].

3. If 1 step is impossible, reduce sorting to a permutation and fix its cycles in 2 steps.
   - With duplicates, we still can build a permutation by matching equal values by occurrence order (stable matching).
   - A permutation decomposes into disjoint cycles.
   - Cycles of length 1 are already correct, length 2 is a swap, and length >= 3 can be resolved in two parallel steps via a standard construction.

---

3. Full solution approach

Step 0: Build the target.
- Read p.
- Let q = sorted(p).
- If p == q, output 0.

Step 1: Try to sort in exactly 1 step.
We greedily build a set of disjoint swaps:
- Maintain used[i] = whether index i is already in a chosen swap.
- For each index i:
  - if p[i] == q[i] or used[i], continue.
  - find some j with !used[j] such that:
    - p[i] == q[j] and p[j] == q[i]
  - if no such j, then 1-step is impossible.
  - otherwise take swap (i, j) and mark both used.

If successful for all mismatches: output 1 and this list.

Complexity: O(n^2) which is fine for n <= 1000.

Step 2: Otherwise, always output a 2-step plan.

2A) Build a permutation perm.
We want perm[i] = the final position (in q) of the element currently at position i in p.

With duplicates, assign occurrences in order:
- For each value x, keep cnt[x] = how many times we have assigned x so far while scanning p.
- Let base = first index of x in q (via lower_bound).
- Then:
  - perm[i] = base + cnt[x]
  - cnt[x]++

This makes perm a true permutation of {0..n-1}.

2B) Decompose perm into cycles and produce swaps in 2 steps.
For each cycle v[0], v[1], ..., v[k-1]:
- k = 1: ignore
- k = 2: put swap (v[0], v[1]) into step 1
- k >= 3: use the construction:
  - Let l = 0, r = k-2
  - while l < r:
    - step 1 add (v[l], v[r])
    - step 2 add (v[l], v[r+1])
    - l++, r--
  - if l == r (odd case), step 2 add (v[l], v[r+1])

All swaps within the same step are disjoint (each cycle index is used at most once per step by construction, and cycles are disjoint).

Finally output 2 and the two steps.

---

4. C++ implementation with comments

```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;
}
```

---

5. Python implementation with detailed comments

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

def check_one_step(p, q):
    """
    Attempt to transform p -> q in exactly ONE parallel step (disjoint swaps).
    For a swap (i,j) to fix both positions immediately:
        p[i] == q[j] and p[j] == q[i]
    Returns (ok, swaps) where swaps is a list of (i,j) 0-based.
    """
    n = len(p)
    used = [False] * n
    swaps = []

    for i in range(n):
        if used[i] or p[i] == q[i]:
            continue

        partner = -1
        for j in range(n):
            if used[j]:
                continue
            if p[i] == q[j] and p[j] == q[i]:
                partner = j
                break

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

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

    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)
        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 perm mapping each index in p to its
    # destination index in q, handling duplicates by occurrence count.
    cnt = defaultdict(int)
    perm = [0] * n
    for i, val in enumerate(p):
        base = bisect_left(q, val)      # first occurrence of val in sorted q
        perm[i] = base + cnt[val]       # choose the cnt[val]-th slot among duplicates
        cnt[val] += 1

    # Decompose perm into cycles and build 2 steps of disjoint swaps.
    turns = [[], []]  # turns[0] = step 1 swaps, turns[1] = step 2 swaps
    vis = [False] * n

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

        # Extract the cycle starting from 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

        # k >= 3: two-step construction
        l, r = 0, 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:  # odd length
            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()
```
