Clearly, the answer is at most \(Q\). So, let us first consider how to determine whether the answer equals \(Q\).

If \(P_1=Q_1\), this value should not be moved throughout. By a similar argument, we see that the common prefix of \(P\) and \(Q\) can be ignored. Below, we assume \(P_1 < Q_1\).

Let \(X_i=P^{-1}(Q_i)\). That is, \(X_i\) is the position of \(Q_i\) within \(P\).

Considering the operations in reverse order, applied to \(Q\), there should exist an index \(i\) satisfying the following conditions.

• \(Q_i>Q_{i+1}\)
• \(X_i>X_{i+1}\)

Let \(Z\) denote the minimum value of such \(i\).

Now, suddenly, let us consider whether there exists an index \(k\) satisfying the following conditions.

• \(k<Z\)
• \(Q_k>Q_{k+1}\)
• \(X_k<X_{k+1}\)
• \(Q_{k+1}<Q_i\) holds for every \(i\) (\(k+2 \leq i \leq N\)) satisfying \(X_i=\min_{k \leq j \leq i} X_j\)

What happens if such a \(k\) exists? First, due to the condition \(k<Z\), a swap at index \(k\) or below cannot happen initially. This becomes possible only after the swap at indices \(k,k+1\) occurs. And the candidates for the value of \(Q_{k+1}\) when we first swap \(k,k+1\) are the \(Q_i\) checked in the fourth condition. However, since \(Q_{k+1}<Q_i\), bringing such a \(Q_i\) to index \(k+1\) would make the entire permutation lexicographically greater than the original \(Q\). That is, if such a \(k\) exists, the operation \(Q \to P\) cannot be performed.

Conversely, it can be proved that if no such \(k\) exists, the operation \(Q \to P\) is possible. For such a procedure, first swap \(Q_Z,Q_{Z+1}\). Then, for each \(t=Z-1,Z-2,\ldots,1\), perform the following operation.

• Among the \(i\)s satisfying \(X_i=\min_{t \leq j \leq i} X_j\), take the one with the minimum \(Q_i\), and move it to index \(t+1\). Then, swap indices \(t,t+1\).

Considering a situation where this operation fails partway through, we see that the \(k\) defined above must exist.

This allows us to determine whether the answer equals \(Q\).

Let us call a permutation \(R\) valid if it is reachable from \(P\) by passing only through permutations at most \(R\). Our goal is to find the lexicographically greatest valid permutation that is at most \(Q\). To do so, we first need to compute how much of the prefix of \(Q\) can be achieved.

For a prefix of length \(L\) (or more) to be achievable, it is necessary for the following condition to be satisfied.

• First, compute \(Z\). If \(Z<L\), the computation will be correct. Otherwise, set \(Z=L\).
• Check whether a \(k\) satisfying the above condition exists. Here, when checking, assume that the values from index \(L+1\) onward are arranged in the most convenient form possible. That is, it is fine if there is just one arrangement in which no \(k\) exists. More specifically, perform the check assuming that index \(L+1\) onward is arranged in decreasing order of \(X_i\).

Let \(Lmax\) denote the maximum \(L\) for which this determination returns true. Here, it should be noted that the above determination states a necessary condition, not a sufficient one. That is, letting \(Lreal\) be the length of the truly achievable prefix, all we immediately know is that \(Lreal \leq Lmax\).

Let us set aside \(Lreal\) for now and find \(Lmax\). Considering performing the determination while incrementing \(L\), we get the following algorithm.

• Suppose we have finished the determination up to a prefix of length \(L-1\), and are now trying to append \(Q_L\) to it.
• Consider a stack \(S\) collecting the current candidate indices for \(k\). An element \(s\) of \(S\) is an index that satisfies the condition for being \(k\) when looking only at the first \(L-1\) terms of the sequence. The condition for \(s\) to not become \(k\) is expressed by some \(w_s,h_s\), meaning that it suffices for there to exist an \(i\) (\(L \leq i\)) satisfying \(X_i < h_s\) and \(Q_i < w_s\). Keep the stack so that elements with larger indices are at the top. Also, by removing candidates that impose weaker conditions, maintain monotonicity of \(w_s,h_s\).
• There are two failure patterns when appending \(Q_L\).
  • (i) When \(X_{L-1}<X_L\) and \(Q_{L-1}>Q_L\): \(L-1\) is newly added as a candidate for \(k\). If there is no \(i\) from the \((L+1)\)-th term onward satisfying \(X_i<X_{L-1}\) and \(Q_i<Q_L\), we know at this point that it fails.
  • (ii) When \(X_{L-1}>X_L\): Focus on the top element \(s\) of \(S\). If appending \(Q_L\) confirms that \(s\) satisfies the condition for being \(k\), we know it fails.
• If neither of the above failure patterns applies, we determine success, increment \(L\), and update \(S\) accordingly.

We wrote earlier that the values of \(Lreal\) and \(Lmax\) differ, but actually, the value of \(Lreal\) can be computed from \(Lmax\) as follows.

• When \(Lmax=N\): this means that \(Q\) itself is achievable as the answer. Naturally \(Lreal=N\).
• When failure occurs with pattern (i): \(Lreal=Lmax-1\).
• When failure occurs with pattern (ii): \(Lreal=Lmax\).

Let us first prove this relationship.

Suppose failure occurs with pattern (i). In this case, \(P^{-1}(v)>X_{Lmax}\) holds for any \(v\) satisfying \(v<Q_{Lmax+1}\). Thus, no matter which \(v\) is adopted as the \((Lmax+1)\)-th element, it will similarly fail with pattern (i). At this point, we know \(Lreal \leq Lmax-1\).

Next, let us show \(Lreal \geq Lmax-1\). Suppose the first \(Lmax-1\) terms are fixed. Take the minimum \(i\) satisfying \(Q_i<Q_{i+1}<\cdots<Q_{Lmax}\), and call it \(m\). If \(m=1\), placing \(P_1\) at the \(Lmax\)-th position yields a valid permutation. If \(1<m\), since it has not yet been determined valid, we know \(X_{m-1}<X_m\). From this, we see that \(m-1\) remains alive as a candidate for \(k\). However, it has not been confirmed that \(m-1\) becomes \(k\). This means there exists an index \(i\) (\(Lmax \leq i\)) satisfying \(X_i < \min_{m-1 \leq j \leq Lmax-1} X_j\) and \(Q_i < Q_m\). By bringing such a \(Q_i\) to the \(Lmax\)-th position, we can obtain a valid permutation. This shows \(Lreal \geq Lmax-1\), and \(Lreal=Lmax-1\) immediately follows.

Next, suppose failure occurs with pattern (ii). By considering this case in the same way as the case \(m>1\) in pattern (i) above, \(Lreal=Lmax\) follows.

This allows us to compute \(Lreal\). Next, let us consider what the \((Lreal+1)\)-th value should be. We can simply try each value one by one, and determine in \(O(1)\) whether each can be appended. This determination can use exactly the same determination used when incrementing \(L\). Let us show that a value passing this determination can actually be used in a valid permutation, by concretely constructing the values from the \((Lmax+2)\)-th position onward.

The values from the \((Lmax+2)\)-th position onward are decided one by one using the following procedure.

• Consider the current top element \(s\) of \(S\). Among the currently unused values less than \(w_s\), let \(v\) be the one that appears earliest in \(P\). Letting \(u\) be the next value to be adopted, we need \(P^{-1}(u) \geq P^{-1}(v)\). So, adopt the maximum \(u\) satisfying \(P^{-1}(u) \geq P^{-1}(v)\).

Remember to update \(S\) each time a value is determined.

We can confirm that if we decide values with this procedure, neither failure pattern is triggered. And this construction clearly achieves the lexicographically greatest valid permutation.

By implementing the above operations, we obtain a solution running in \(O(N \log N)\) time.

As a side note, when computing “among the currently unused values less than \(w_s\), the one that appears earliest in \(P\),” it can actually be shown that the condition “currently unused” does not need to be considered, that is, \(v\) can be determined for each \(w_s\) from the beginning. The writer’s solution simplifies the implementation using this fact.

Sample Solution (C++)