Sorting a Permutation via Tree Swaps

You are given a permutation (x) of (q) elements, i.e. a rearrangement of the numbers (1,2,\ldots,q). The only allowed operation is as follows: for any valid index (i) (such that at least one child exists), you may swap (x_i) with either (x_{2i}) or (x_{2i+1}) (if those indices exist). Your task is to transform (x) into an ascending sequence, i.e. to achieve (x_1 < x_2 < \cdots < x_q) (which for a permutation is equivalent to (x_i=i) for all (i)).

In addition, you must output the operations in the order they are performed. Each operation is represented by two indices: the first is the index where the operation is applied (i.e. the parent index) and the second is the child index chosen (either (2i) or (2i+1)).

For example, if you perform an operation on index (i) with child index (j), the values (x_i) and (x_j) get swapped. Use LaTeX formatting for all formulas (for example, (x_i), (2i), etc.).

It is guaranteed that a sequence of such operations exists that transforms the given permutation into sorted order. If there are multiple valid solutions, you may output any.

inputFormat

The input begins with a line containing a single integer (q) (the length of the permutation). The next line contains (q) space‐separated integers (x_1,x_2,\ldots,x_q) which form a permutation of ({1,2,\ldots,q}).

outputFormat

First, output an integer (k) representing the total number of operations performed. Then, output (k) lines, each containing two space‐separated integers (i) and (j) indicating that an operation is applied at index (i) (swapping (x_i) with (x_j), where (j) is either (2i) or (2i+1)). The sequence of operations must transform the permutation into sorted order.

sample

3
2 3 1

4
1 3
1 2
1 3
1 2