AtCoder shananigans

Here is the problem, and below is the raw transcript of my thoughts.

Obs: It is always optimal to use all $K$ moves.

intuitive proof. While we have moves left, each move can be used to improve the permutation. Either we can shorten it if all are in increasing order.

Or we can improve it if we have say 1 4 2 by deleting the 4.

we want to prioritise getting 1 in first position

Suppose $1$ has $p[1]=1$. If we shift, we are worsening our permutation.

So shifts become useless. Once the 1, or the lowest value possible is

positioned at the head, we will only use deletes.

We have some options for _ ... _ 1 _ ... _ to be improved

1. Delete the prefix.

2. Shift $1$ to the head.

3. Delete part of the suffix and then shift $1$ to head.

If we are going to shift, we should delete from the suffix first.

Otherwise we waste moves shifting values that will be deleted.

We can simulate this by shifting first without deleting, then

anything in the suffix before the shift can be deleted for free.

As long as we take this into account, we can ignore $3$ and just do $2$.

Sub-Problem: Given a permutation how to optimally improve it with

only deletes. Just delete whenever there is a decrease so for example:

1 3 2 4 we would first delete the $3$, then the $4$. We can use a stack to push values to while they increase and as soon as we see a decrease, we pop until it goes back to increase.