Permutations and Queries

Let $D=\left\lceil\cfrac{N}{2}\right\rceil$ and $L=D-1$. The minimum allowed interval length is $L$.

1. Swapping two distant positions

Suppose $x<y$ and $y-x\geq D$. Reverse the following two intervals in order.

$[x,y]$ $[x+1,y-1]$

The first reversal exchanges the two endpoints and reverses the interior. The second reversal restores only the interior. Therefore, only the elements at positions $x$ and $y$ are exchanged.

The second interval has length $y-x-1\geq D-1=L$, so both reversals are allowed. When $N=2$ and the two positions are adjacent, reversing only $[x,y]$ is sufficient.

2. A coordinate system with one fixed endpoint

First use position $1$ as the endpoint. Let $R$ be the reversal of $[2,N]$. It fixes position $1$ and maps every other position $x$ to $N+2-x$.

The two distances

$$x-1,\qquad N+1-x$$

sum to $N$. Therefore, at least one of them is at least $D$. If $x$ is too close to position $1$ in the current coordinate system, applying $R$ once makes it sufficiently far away.

Treat the state after applying $R$ as another coordinate system. Only the actual position representing each logical position changes. Swapping two actual positions in that coordinate system swaps the corresponding logical positions. One Boolean value is enough to remember whether this coordinate system is reversed.

The construction for endpoint $N$ is symmetric and uses the reversal $[1,N-1]$.

3. A cycle containing the endpoint

Consider a permutation cycle

$$(c_1,c_2,\cdots,c_k)$$

where $P_{c_i}=c_{i+1}$ and $P_{c_k}=c_1$. Suppose $c_1$ is the current endpoint.

Swap the following pairs of logical positions in order:

$$(c_1,c_2),(c_1,c_3),\cdots,(c_1,c_k).$$

These swaps fix every position in the cycle.

Before each swap, if the other position is too close to the endpoint, apply the auxiliary reversal $R$ once. The two positions can then be exchanged with two reversals. The $k-1$ swaps require $2k-2$ reversals. Coordinate-system changes are needed at most once before each swap and at most once more at the end, for at most $k$ changes.

Thus, a cycle of length $k$ containing the endpoint can be processed using at most

$$(2k-2)+k=3k-2$$

reversals.

4. A cycle not containing an endpoint

Choose an initial position $c_1$ of the cycle.

If $c_1\geq L$, reverse $[1,c_1]$. This reversal is allowed and maps logical position $c_1$ to actual position $1$.

If $c_1<L$, reverse $[c_1,N]$. This reversal is also allowed and maps logical position $c_1$ to actual position $N$.

Process the cycle in this coordinate system using the previous construction, and then reverse the initial interval again to restore the original coordinate system. The first and last reversals add two operations, so a cycle of length $k$ needs at most

$$1+(3k-2)+1=3k$$

reversals.

5. Total number of operations and implementation

Cycles of length $1$ require no operation. Process every other cycle independently. The sum of their lengths is at most $N$, so the total number of reversals is at most $3N$.

In the implementation, compute the cycle decomposition of the permutation. For each cycle, maintain the selected endpoint, the initial coordinate transformation, and one Boolean value for the auxiliary reversal. There is no need to simulate the entire array.

The time complexity excluding the printed output is $O(N)$, and the number of printed operations is $O(N)$.

Solution written by GPT5.6