Description

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.

Input Format

The input has a total of $2$ lines.

Line $1$ contains $1$ positive integer $q$.

Line $2$ contains $q$ positive integers, $x_{1～q}$.

Output Format

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)$.

3
3 1 2

1 3
1 2

7
1 3 2 7 6 4 5

2 4
1 2
1 3
3 7
2 5
1 2
1 3
3 6
1 2
2 5
1 3
1 2
2 4
1 2
1 3
1 2

Hint

[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