Preface

In this editorial, we call the former operation a deletion and the latter a rotation.
In this operation, you are allowed to perform operations between \(0\) and \(K\) times, but you can always obtain a lexicographically smaller sequence by an operation, so you actually perform exactly \(K\) operations. Specifically, if you have a sequence after less than \(K\) operations, you may use the remaining chances of operations to obtain a lexicographically smaller sequence by removing the final term.

If a rotation is not performed

First, we consider the lexicographically smallest \(P\) obtained by performing only deletion between \(0\) and \(K\) times. The candidates of the initial term of resulting \(P\) is \(p_1,p_2,\ldots,p_{K+1}\). (As we can perform deletions at most \(K\) times, \(p_{K+2}\) and subsequent terms cannot end up in the head.) Since the lexicographical order first compares the first term, the smallest of the candidates should be selected as the initial term. We apply the same rule for the \(2\)-nd and subsequent terms.
Doing this simulation naively requires finding the minimum value of at most \(N\) values at most \(N\) times. This costs \(\mathrm O (N^2)\) time, which exceeds the time limit. So why we need some optimization like using Segment Trees.

If a rotation is performed once or more

We first show several properties.

• Removing a term that has been moved by a rotation does not make sense because we can just remove the term before the rotation to accomplish the same objective in one operation.
• We may perform deletions and rotations in any order, but the lexicographically smallest \(P\) can be obtained by the following order:
  • First, perform \(0\) or more rotations.
  • Then, perform \(0\) or more deletions. Deleting a term that was moved by the rotations we did before does not count in the number of operations. (We regard it was removed instead of being rotated)

By the second property, the correct answer can be obtained by simulating the cases involving \(1,\ldots,K\) rotations each in the same way as we did in the no-rotation case we described, but the time complexity is \(\mathrm O(N^2 \log N)\). Here, considering the first property, we can say that, after a rotation is performed at least once, the initial term is never removed, so we only have to consider the rotations that minimizes the initial term. Therefore, it is sufficient to perform the simulation for two cases involving and not involving rotations and to output the lexicographically smaller one.

Bonus

While the simulation can be done in a total of \(\mathrm O(N \log N)\) time with a Segment Tree, we can use “minimum value in sliding window” technique to reduce the time complexity to \(\mathrm O(N)\).