Restoring Memory Order via Unique Swap Instructions

You are given a computer with n memory cells and infinitely many registers. The memory cells are numbered from 1 to n and initially contain a permutation of the numbers 1 through n (each appearing exactly once). The registers are numbered starting from n+1 and each register i initially stores the integer i.

The computer supports only one type of instruction: swap i, j, which exchanges the contents of positions i and j (both positive integers, with i ≠ j). However, every swap instruction must involve at least one register (i.e. at least one of i or j must be greater than n).

There is an additional quirky bug: the computer will not execute the same swap instruction more than once. Two instructions are considered the same if they involve the same pair of positions regardless of order (for example, swap 3, 7 and swap 7, 3 are identical).

Your task is to design a sequence of swap instructions that, when executed in order, restore every memory cell and register to its correct value (i.e. position i holds the integer i). Moreover, you must accomplish this while using as few registers as possible; that is, the maximum register index that is actually used in any swap should be minimized.

Hint: It can be shown that if the initial memory permutation isn’t already sorted, one can decompose it into cycles. A transposition (swapping two memory cells) can be simulated using swap instructions that involve registers. However, you are not allowed to perform a direct swap between two memory cells, and you must also avoid repeating any swap instruction. For a 2‐cell swap (transposition), one valid simulation using two registers (say, R1 = n+1 and R2 = n+2) is as follows:

swap(i, R1)
swap(j, R2)
swap(R1, j)
swap(i, R2)
swap(R1, R2)

This sequence exchanges the contents of memory cells i and j and then restores the registers to their original values, while each instruction uses at least one register and no two instructions are identical. For a cycle of length L (with L ≥ 2) one may fix it by making L-1 such transpositions using the first element of the cycle as a pivot. In order to avoid repeating swap instructions (for example, the pair swap(R1,R2) cannot be used twice), you need to use a unique pair of registers for each transposition. That is, if the total number of transpositions is T then you can use registers numbered from n+1 to n+2T by assigning for the k^th transposition:

Let R_a = n + (2*k-1) and R_b = n + (2*k).

Apply the 5-swap simulation above with these registers. Doing so for each transposition (i.e. each pair swap between the pivot and another cell in the cycle) will eventually sort the memory cells while restoring every register to its original content.

Your program must output a valid sequence of swap instructions that achieves this goal.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of memory cells. The second line contains n space‐separated integers, which represent the initial contents of the memory cells; they form a permutation of the numbers 1 through n.

outputFormat

First, output an integer m — the total number of swap instructions in your sequence. Then, output m lines, each line containing two positive integers i and j (with i ≠ j), indicating that the computer should execute swap i, j at that step. Every swap must involve at least one register (i.e. at least one of i or j must be greater than n), and no swap instruction (considered as an unordered pair) may appear more than once.

sample

3
2 3 1

10
swap 1 4
swap 2 5
swap 4 2
swap 1 5
swap 4 5
swap 1 6
swap 3 7
swap 6 3
swap 1 7
swap 6 7