P7128 "RdOI R1" Sequence (sequence)

There is a sequence $x$ of length $q$, and each number in the sequence appears exactly once. That is, the sequence $x$ is a permutation of $1$ to $q$. There is only one allowed operation on sequence $x$: for a number $x_i$, you may swap it with $x_{2i}$ or $x_{2i+1}$ (if they exist). Now, please turn sequence $x$ into an increasing sequence, and output the operations you perform in order.

The input has a total of $2$ lines. Line $1$ contains $1$ positive integer $q$. Line $2$ contains $q$ positive integers, $x_{1～q}$.

The output has a total of $ans$ lines, where $ans$ is the number of operations you perform. Lines $1$ to $ans$ each contain two integers $i$, $j$, meaning to swap the positions of $x_i$ and $x_j$ $(i < j)$.

[Sample Explanation] Explanation of Sample #1: Swap $2$ and $3$, and the sequence becomes: $2,1,3$. Then swap $2$ and $1$, and the sequence becomes: $1,2,3$. [Constraints] For $40\%$ of the testdata, $3 \le q \le 2^{10}$. For $100\%$ of the testdata, $3 \le q \le 2^{17}$, $1 \le x_i \le q$. [Hint] - Use Special Judge. - $q = 2 ^ p - 1(p \in \mathbb{N}^*)$. - Perform at most $2q\times\lceil\log_2 q\rceil$ operations. - The sample output is just one of many possible solutions. - Because it is `special judge`, no additional samples are provided. --- [File Input/Output] **(Simulation, not needed when submitting code)** - File name: `sequence.cpp`. - Input file name: `sequence.in`. - Output file name: `sequence.out`. Translated by ChatGPT 5