<|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 (concise)

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 (detailed comments)

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

/*
  Multiswap Sorting (minimum steps).
  Key fact: answer is always 0, 1, or 2.

  Strategy:
    1) q = sorted(p). If already sorted -> 0.
    2) Try to sort in 1 step by greedily pairing indices (i,j) such that:
         p[i] == q[j] and p[j] == q[i]
       and all indices are used at most once.
       If possible -> 1.
    3) Otherwise construct a permutation perm mapping each current index to its
       destination in q (handling duplicates by occurrence count), decompose
       perm into cycles, and output a known 2-step swap plan for each cycle.
*/

static pair<bool, vector<pair<int,int>>> check_one_step(
    const vector<int>& p, const vector<int>& q
) {
    int n = (int)p.size();
    vector<bool> used(n, false);
    vector<pair<int,int>> swaps;

    for (int i = 0; i < n; i++) {
        // If i is already correct or already involved in a swap, skip it.
        if (used[i] || p[i] == q[i]) continue;

        int partner = -1;
        // Find j such that swapping i and j makes both positions correct.
        for (int j = 0; j < n; j++) {
            if (used[j]) continue;
            if (p[i] == q[j] && p[j] == q[i]) {
                partner = j;
                break;
            }
        }

        // If we can't find a partner for some mismatched i, 1 step is impossible.
        if (partner == -1) return {false, {}};

        used[i] = used[partner] = true;
        swaps.push_back({i, partner});
    }

    return {true, swaps};
}

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

    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];

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

    // 0 steps if already sorted
    if (p == q) {
        cout << 0 << "\n";
        return 0;
    }

    // Try 1-step solution
    auto [ok1, swaps1] = check_one_step(p, q);
    if (ok1) {
        cout << 1 << "\n";
        cout << swaps1.size();
        for (auto [i, j] : swaps1) {
            // Output is 1-based indices
            cout << " " << (i + 1) << " " << (j + 1);
        }
        cout << "\n";
        return 0;
    }

    // Otherwise build a permutation perm: perm[i] is the target position in q
    // for the element currently at i in p. Handle duplicates using occurrence counts.
    vector<int> perm(n);
    map<int,int> cnt; // cnt[value] = assigned occurrences so far while scanning p

    for (int i = 0; i < n; i++) {
        int val = p[i];
        int base = int(lower_bound(q.begin(), q.end(), val) - q.begin());
        perm[i] = base + cnt[val];
        cnt[val]++;
    }

    // turns[0] = step 1 swap list, turns[1] = step 2 swap list
    vector<pair<int,int>> turns[2];

    // Decompose permutation into cycles.
    vector<bool> vis(n, false);
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;

        vector<int> cycle;
        int u = i;
        while (!vis[u]) {
            vis[u] = true;
            cycle.push_back(u);
            u = perm[u];
        }

        int k = (int)cycle.size();
        if (k == 1) continue;

        if (k == 2) {
            // A 2-cycle is fixed by a single swap; put it into step 1.
            turns[0].push_back({cycle[0], cycle[1]});
        } else {
            // k >= 3: two-step construction
            int l = 0, r = k - 2;
            while (l < r) {
                turns[0].push_back({cycle[l], cycle[r]});       // step 1
                turns[1].push_back({cycle[l], cycle[r + 1]});   // step 2
                l++;
                r--;
            }
            if (l == r) {
                // odd length: one extra swap in step 2
                turns[1].push_back({cycle[l], cycle[r + 1]});
            }
        }
    }

    // Output 2 steps (always optimal here)
    cout << 2 << "\n";
    for (int t = 0; t < 2; t++) {
        cout << turns[t].size();
        for (auto [i, j] : turns[t]) {
            cout << " " << (i + 1) << " " << (j + 1);
        }
        cout << "\n";
    }

    return 0;
}
```

---

## 5) Python implementation (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()
```

