Since I made a blog for E here : https://codeforces.me/blog/entry/155193 I might as well go ahead and do another one for another problem. This one is simpler but the editorial is still quite unintuitive an complex so I will share my own idea here.

The problem :

• Given a $$$n$$$ and $$$P, Q$$$ is two permutation of $$${1, 2, ..., n}$$$, $$$P \lt = Q$$$ lexicographically
• Can perform some number of operation in $$$P$$$ (operation $$$swp$$$) : Swap 2 values of $$$P$$$ that is currently adjacent (1) and never swapped with each other before (2) to transform $$$P$$$ into permutation $$$P'$$$, such that $$$P' \lt = Q$$$ lexicographically (3)
• Find the maximum lexicographically $$$P$$$ can transform into.

The condition (2) basically force us that if we intend to transform $$$P$$$ into $$$R \lt = Q$$$, we must transform it with minimum number of swap when not restrict by (3).

We can assume $$$Q[0] \neq P[0]$$$ since if not we will ignore them entirely.

Define some structure :

• $$$s_1, ..., s_t$$$ represent we swapping index $$$s_i, s_i + 1$$$ of $$$P$$$ at $$$i-th$$$ operation
• $$$pos_0, pos_1,..., pos_t$$$ is the array such that $$$pos_i[j]$$$ is position of $$$P[j]$$$ in $$$Q$$$ after we performed $$$i$$$ operations
• $$$pref_0, pref_1,..., pref_t$$$ with $$$pref_i$$$ being the length of longest common prefix of $$$P$$$ and $$$Q$$$ after $$$i$$$ operations
• $$$diff_0, diff_1,..., diff_t$$$ is $$$pos_i[pref_i]$$$, represent the Q-index of the first different values in the same position of $$$P$$$ and $$$Q$$$ after $$$i$$$ operations, or $$$n$$$ if $$$pref_i = n$$$, i.e $$$P = Q$$$. Note that $$$diff_i = n$$$ or $$$Q[diff_i] \lt Q[pref_i]$$$ for (3) to hold

To make the $$$P$$$ transform into the largest lexicographically possible, we first must make $$$pref_t$$$ as large as possible. Observe some optimization of optimal transforming sequence we can deduce that :

• $$$pref_{i + 1} \gt = pref_i$$$ and if $$$pref_{i + 1} \gt = pref_i + 2$$$, $$$i + 1 = t$$$ (4)

We see that if $$$pref_{i + 1} \lt p = pref_i$$$ $$$pref_t \lt p$$$ since we can't increase $$$pref$$$ anymore else it will involve swapping two elements already swapped, but it will be better if we just replace operation sequence $$$s_1, ..., s_t$$$ with $$$s_1, ..., s_i$$$.

And if $$$pref_{i + 1} \gt = pref_i + 2$$$, meaning $$$s_{i + 1} = pref_i$$$ and $$$pos_i[pref_i] = pref_{i} + 1$$$ and $$$pos_i[pref_{i} + 1] = pref_i$$$. But then we know $$$s_j \gt pref_i$$$ since future swap won't be touching the common longest prefix elements so the swapping operation sequence $$$s_1, ..., s_{i - 1}, s, s_{i + 1},... s_t$$$ can be replaced with $$$s_1, ..., s_{i - 1}, s_{i + 1},..., s_t, s_{i}$$$ and it won't violate (3) and still produce the same permutation.

We will find the largest value of $$$mx = pref_t$$$, we see that $$$mx$$$ must satisfy $$$min(Q[mx, n - 1]) \lt Q[mx]$$$ or $$$mx = n$$$ else there won't exist a permutation having exactly first $$$mx$$$ element matched with $$$Q$$$ but the $$$mx-ith$$$ element smaller than that of $$$Q$$$ (5).

We will also prepare a list $$$g$$$ and observe that :

• For $$$i \lt t$$$ such that $$$pref_i = pref_{i - 1} + 1 = p + 1$$$, $$$s_i = p$$$ and $$$pos_{i - 1}[p + 1] = p$$$, $$$Q[pos_{i - 1}[p]] \lt min(Q[p], Q[p + 1]$$$. We prepare a a list $$$g$$$ and push in the pair $$$(pos_{i - 1}[p], p)$$$ with every such $$$i$$$, i.e pair of current first element differ from $$$P$$$ and $$$Q$$$ after $$$i - 1$$$ swap and the element swapping to increase the length of common prefix.

• For $$$i \lt t$$$ such that $$$pref_i = pref_{i - 1} = p$$$, and $$$s_i = p$$$, which mean $$$diff_{i - 1} \neq diff_{i}$$$ we record pair $$$diff_{i - 1}, diff_{i}$$$ i.e the change of the first element differ between $$$P$$$, $$$Q$$$.

$$$g$$$ will have the form $$$(d_1, d_2), (d_2, d_3),..., (d_v, 0), (d_v, d_{v + 1}), ...., (d_{v'}, 1), ....)$$$ with the element $$$(d_i, j)$$$ represent the moment $$$pref$$$ got increased by 1.

We can shorten the list $$$g$$$ into list $$$g' = (d_1, d_2), (d_2, 0), (d_2, d_3), (d_3, 1), ..., $$$ i.e the $$$diff$$$ values only change at most 1 time between the change of $$$pref$$$ value. We will also put equal pair represent $$$diff$$$ didn't change before $$$pref$$$ change, for example $$$d_2 = d_3$$$ meaing after $$$pref$$$ got increase from $$$0$$$ to $$$1$$$, the first element differ from $$$P$$$ and $$$Q$$$ just stay at $$$1-index$$$ position waiting $$$Q[1]$$$ to swap with it to increase $$$pref$$$.

We can easily see that the shorten list $$$g'$$$ corresponded to an operation swapping sequence $$$s'$$$ that can produce any permutation some sequence $$$s$$$ corresponding to $$$g$$$ can produce.

Supposed $$$g'$$$ has size $$$2 * sz$$$ : $$$(d_1, d_2), (d_2, 0), (d_2, d_3), (d_3, 1), ..., (d_{sz + 1}, sz - 1)$$$, that mean $$$pref$$$ will increase from $$$0$$$ to $$$sz$$$ before the last swapping operation $$$s_t$$$ and with last operation $$$s_t$$$, it will increase from $$$sz$$$ to $$$mx$$$. (**)

We see that between all pair $$$d_i, d_{i + 1}$$$, $$$d_i$$$ is either $$$ \gt = mx$$$ meaning $$$Q[d_i]$$$ won't appear as a element of longest common prefix, or $$$d_j \lt d_i \lt mx$$$ for all $$$j \lt i$$$ since if not we either swapped with non-common prefix element to a common prefix element, or two common prefix element to put them incorrectly ordered and won't be able to switch back.

We see that for pair (d_i, i — 2) to appear, meaning $$$Q[d_i] \lt min(Q[d_{i - 2}], Q[d_{i - 1}])$$$ and if when making a swap $$$(d_i, d_{i + 1})$$$, if $$$d_i \gt mx$$$. To have such $$$d_i$$$, when choosing the pair $$$(d_{i - 1}, p = d_i$$$ when an already chosen $$$d_{i - 1}$$$, we can greedy choose leftmost $$$p = d_i$$$ satisfied $$$Q[p] \lt min(Q[d_{i - 2}], Q[d_{i - 1}])$$$ in the current $$$pos$$$ array such that : (6)

• If $$$d_{i - 1} \lt mx$$$ then $$$p$$$ is chosen between the index $$$ \lt d_{i - 1}$$$
• If not we will try to choose it between the indexes $$$ \gt = mx$$$ first, if not possible then choosing between indexes $$$ \lt mx$$$, else there will.

We can see that if the array $$$g'$$$ choosed greedily like this, if the general $$$g'$$$ can increase $$$pref$$$ to $$$sz$$$ then this strategy will also can increase $$$pref$$$ to $$$sz$$$, and the constraints involving (2) before $$$pref$$$ increase to $$$sz$$$ is a subset of constraint of the general $$$g'$$$ involving indexes $$$ \lt = mx$$$ so we can also arrange $$$mx, mx + 1,... sz-1$$$ follow directly the common prefix to make a prefix size $$$sz$$$ if the general $$$g'$$$ can do so.

So we can determinate that for $$$mx$$$ to be a possible common longest prefix length, it must be possible to produce by (6), and satisfy (5). We see that if $$$mx$$$ sastifies (6) then $$$mx - 1$$$ also sastifies, algo (6) can be run in $$$O(nlg(n))$$$ so performing binary search we can find maximum $$$sz$$$ sastify (6) in $$$O(nlg^2(n))$$$ and check the largest value below that threshold sastify (5). So in the end we found the value $$$mx$$$.

Since we found the value $$$mx$$$ of longest prefix, we now try to optimize the element indexes $$$mx, mx + 1, ..., n - 1$$$ of final array. Observe the process (**) of how a general $$$g'$$$ produce an optimized permutation, the subarray containing all the record the time $$$pref$$$ increase by $$$1$$$ $$$g" = ..., (d_i, i - 2), ...$$$ we will try to find the smallest $$$i$$$ such that there is an array $$$g$$$ such that the bold element $$$(d_i, i - 2)$$$ having $$$d_i \lt mx$$$. That means $$$g'$$$ will have the form $$$(d_1, d_2), (d_2, 0), (d_2, d_3), (d_3, 1), ..., (d_{i - 1}, D_i), (D_i, i - 2), ..., (D_{sz + 1}, sz - 1)$$$ such that all $$$D_i, D_{i + 1}, ..., D_{sz + 1}$$$ is all $$$ \lt mx$$$. We see that with minimal $$$i$$$ determinated, $$$D_i,... D_{sz + 1}$$$ can be found independably with a $$$O(nlg(n))$$$ dp from $$$d_1, d_2,..., d_{i - 1}$$$ if it satisfied the general condition that $$$Q[d_i] \lt min(Q[i - 2], Q[i - 1])$$$ and if $$$d_i = d_j$$$ with $$$i \lt j$$$ then $$$d_i = d_{i'} = d_j$$$ with all $$$i \lt j' \lt j$$$ (***).

Next we will find an array $$$d_1, d_2,... d_{i - 1}$$$ satisfied (3) so that the constraint involving (2) will produce the optimal array permutation of $$$Q[mx, n - 1]$$$. We see that array $$$D[0, i - 1]$$$ such that $$$d_i = pos_0[D_i]$$$, then the constraint involving (2) will contain all the constraint : index $$$pos_0[D_i]$$$ has swapped with every $$$pos_0[L]$$$ indexes such that $$$L \lt D_i$$$ except when $$$pos_0[L] \lt i - 1$$$.

So oberseve a permutation $$$Q'$$$ of $$$Q[mx, sz - 1]$$$ and process each element $$$Q'[i]$$$ that can be as large as possible, we see that $$$Q'$$$ is reachable by array $$$d_1, d_2, ..., d_{i - 1}$$$ by the following process :

• Current state is $$$(d_{i - 1}, i - 1)$$$
• Process each element $$$q$$$ of $$$Q'$$$ from left to right
  • If current state is $$$(d, i')$$$, if $$$i' = 0$$$, $$$Q'$$$ is accepted
  • If $$$0 \lt i' \lt = i - 1$$$, if $$$q \gt Q[d]$$$ continue
  • If $$$q \lt Q[d]$$$ $$$Q'$$$ is not accepted
  • If $$$q = Q[d]$$$, change the current state from $$$(d, i')$$$ to $$$(d_{i' - 1}, i' - 1)$$$.

The sequence of states $$$(d_{i - 1}, i - 1), ..., (d_1, 1)$$$ must sastify (***), we will use dp to realize that state $$$(u, id)$$$ sastify that there is a sequence of $$$(d_1, 1), (d_2, 2),... (d_{id - 1}, id - 1), (u, id)$$$ sastify (***) then there is a range $$$L_id, R_id, H_id$$$ such that it hold iff $$$L_id \lt = u \lt = R_id; Q[u] \lt = H_id$$$, and $$$L_id \gt = L_{id - 1}$$$, same with $$$R$$$.

So we will try to emulate all the possible states $$$(d, i')$$$ possible after processing some prefix of optimal permutation of $$$Q'$$$ currently by set of range $$$(L'_{id}, R'_{id}, id)$$$ meaning the state $$$(u, id)$$$ is reachable from that prefix iff $$$L'_{id} \lt = u \lt = R'_{id}, u \lt = H_id$$$. We will start will a single state of $$$(L_{i - 1}, R_{i - 1}, i - 1)$$$ representing all the possible $$$d_{i - 1}$$$ that can be the last element of an array $$$d$$$ satisfied (***).

When process an element $$$q$$$, the state $$$L'_j, R'_j, j$$$ will be removed if $$$q \lt L'_j$$$, or if $$$L'_j \lt = q \lt = R'_j$$$, $$$R'_j$$$ will be cut into $$$min(R'_j, q - 1)$$$ then if $$$Q[q] \lt H_j$$$ then we will extent $$$L'_{j - 1}, R'_{j - 1}$$$ (or create one if not exist) to $$$R'_{j - 1} = max(R'_{j - 1}, q - 1)$$$. That represent state $$$(q, j)$$$ turn into any state $$$(q', j - 1)$$$ with $$$q \gt q' \gt = L_{j - 1}$$$ and $$$Q[q'] \lt H_{j - 1}$$$.

We see that above process persevere that $$$L'_i \gt = L'_{i - 1}$$$ and same with $$$R'_i$$$, with the extent part only applied for at most one segment of index $$$j$$$ and any other segment of index $$$j' \gt j$$$, we only need to apply cut operation and ignore the extent one since both $$$L'_{j'}$$$ and $$$L'_{j'-1}$$$ $$$ \gt = q - 1$$$.

So general process we will do is that storing all the elements of $$$Q[mx, n - 1]$$$ into a set, each time consider the largest element possible (with additional condition that first element we will use must < $$$Q[mx]$$$), then use that element to operate on the set of segments. If all the segments got removed meaning we can't append that element into the current optimal suffix of permutation of $$$Q[mx, n - 1]$$$, put it back to the set and process the next largest element. Else remove that element from set and begin anew with updated segments. This process is guarantee to end since there exist at least one permutation of $$$Q[mx, n - 1]$$$ to append after common prefix of length $$$mx$$$. So we find the optimal permutation in $$$O(nlg^2(n))$$$.