Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Aaeria

Hint

In what cases will operating on a digit increase the number?

When the digit is larger than the one after it.

Hint

The earlier digits always make a bigger difference than the later ones.

Solution

Given moves, Lookcook should move back the first digits that are larger than the digit after it. These digits can be found by keeping a monotonically nondecreasing stack. After finding these values, move them in nondecreasing order (move the smallest of the digits first and the largest last). This takes time for an digit number.

Example

1
26451689
5

is bigger than . So should be a digit that gets moved. The resulting number is .

is bigger than , so it should be moved. The resulting number is .

Now that is directly after , should be moved. This leaves .

Now that is directly after , should be moved. This leaves .

is the last element. But we know that we will move to the end, and it will be smaller than . So should also be moved, leaving .

Should be moved for the same reason as , but we've used up all our operations, so we stop now.

The digits we've selected are . They should be moved in the non-decreasing order , giving the result as .