Comparable Permutations

Let $i$ be the first index where $q$ differs from $p$, and let $j$ be the last index where they differ. Then

$q>p$

is decided at $i$, so we need $q_i>p_i$. The reversed comparison is decided by the last changed original position, so we also need

$q_j>p_j.$

Everything before $i$ and after $j$ stays unchanged. So the core task is: choose an interval $[i,j]$ and rearrange its values so both endpoints increase.

For a fixed interval $[i,j]$, this is possible iff neither $p_i$ nor $p_j$ is the maximum of $p[i..j]$.

If $p_i$ is the maximum, position $i$ cannot be increased. Same for $p_j$. Conversely, if neither endpoint is maximum, put the smallest value in the interval that is greater than $p_i$ at position $i$, then put all remaining interval values in increasing order. The last position gets the largest remaining value. If the moved first value was not the maximum, the maximum lands at $j$ and beats $p_j$. If it was the maximum, then $p_i$ was the second maximum, so the last value is $p_i$, still larger than $p_j$.

Now optimize lexicographically. The later the first changed position is, the smaller the whole permutation is. So we want the largest possible $i$.

A valid interval exists starting at $i$ exactly when there is an internal maximum somewhere after it. In particular, if $k$ is a local maximum,

$p_k>p_{k-1}\quad\text{and}\quad p_k>p_{k+1},$

then $i=k-1$ works using the tiny interval $[k-1,k+1]$.

Take the last local maximum $k$. Then $i=k-1$ is optimal. No $i\ge k$ can work: after the last local maximum, the suffix has no peak, meaning its adjacent comparison pattern is some decreases followed by some increases. Any interval inside such a valley-shaped sequence has its maximum at an endpoint, which kills the endpoint-increase condition. No last local maximum means no answer. Simple, brutal, done.

Now we need construct the actual index permutation using at most $3n$ queries.

Ask all adjacent comparisons and store

$up[x] = [p_x < p_{x+1}].$

Then $k$ is the largest index with $up[k-1]=1$ and $up[k]=0$. Let $s=k-1$ be the first changed position.

We need the values in $p[k..n]$ sorted. Since there is no local maximum after $k$, this suffix is decreasing, then increasing. So it is two sorted lists if we reverse the decreasing part:

• indices from the valley-left side, walked right-to-left;
• indices from the increasing side, walked left-to-right.

Merge those two lists using comparison queries. This gives order, the indices $k,k+1,\dots,n$ sorted by their hidden values.

Now binary search in order for the first value greater than $p_s$. That index becomes $r_s$. Then replace that position inside order with $s$, and write the rest of order after position $s$. This is exactly: put the successor of $p_s$ first, then put all remaining suffix values in increasing order.

Query count:

• $n-1$ adjacent comparisons;
• at most $n-1$ comparisons to merge;
• at most $\lceil\log_2 n\rceil+1$ comparisons for binary search.

That is safely within $3n$. Memory is $O(n)$.