Portal

Research note: I checked the official Codeforces editorial for 2200D, which gives the same core construction: separate outside/inside, rotate the inside to its minimum, then insert it into the outside sequence before the first larger element. Source: https://codeforces.com/blog/entry/151625

Write the current state as

$L\ \mathcal O\ B\ \mathcal O\ R$,

where $B$ is the segment between the portals, and $L,R$ are outside the portals.

Initially:

• $B = [p_{x+1}, p_{x+2}, \dots, p_y]$ using 1-indexing,
• $A = L + R = [p_1,\dots,p_x,p_{y+1},\dots,p_n]$.

Now look at what operations really do. No magic sorting portal, sadly.

• Moving the element left of the left portal to the right of the right portal changes the split between $L$ and $R$, but $L+R$ stays the same sequence.
• Moving the element right of the right portal to the left of the left portal also changes only that split, again preserving $L+R$.
• Moving an element adjacent to the inside of a portal just rotates $B$: first element to the end, or last element to the front.

So the invariant is:

$A = L+R \text{ never changes as a sequence},$

and

$B \text{ can only become a cyclic rotation of itself}.$

Also, every such state is reachable: slide the portals through $A$ until the insertion position is where you want, and rotate $B$ until the desired rotation is between them.

Therefore every reachable final permutation is exactly:

$A[0..k-1] + \operatorname{rot}(B) + A[k..|A|-1]$

for some insertion position $k$ and some cyclic rotation of $B$.

Now optimize lexicographically.

Let $m = \min(B)$. Since all values are distinct, the lexicographically best rotation of $B$ must start with $m$. Any other rotation starts with some $c>m$, and when comparing optimized answers, the one starting with $m$ wins at the first position where the inserted block can matter. No need to overthink it: smallest first element is king.

So construct

$C = B \text{ rotated so that } C_1=m.$

Now choose where to insert $C$ into $A$.

If an outside element $A_i < m$, placing $m$ before it is worse than leaving $A_i$ first. So all initial outside elements smaller than $m$ should remain before $C$.

The first time we see $A_i > m$, inserting $C$ before it is better, because $m < A_i$. Waiting any longer would keep that larger element before $m$, which is obviously worse.

So the answer is:

1. output the longest prefix of $A$ whose elements are $<m$;
2. output the rotated block $C$;
3. output the rest of $A$.

Edge cases are naturally handled:

• if $A$ is empty, the answer is just the best rotation of $B$;
• if all elements of $A$ are smaller than $m$, insert $C$ at the end;
• if the first element of $A$ is greater than $m$, insert $C$ at the beginning;
• if $B$ has length $1$, rotating it changes nothing.

The total work per test case is linear: we scan the permutation, find the minimum in $B$, rotate by copying, and merge.

Complexity:

$O(n)$ per test case, and $O(n)$ memory. Over all tests, this is $O(\sum n)$.