## Editorial for Canada Day Contest 2021 - CCC Bad Haha

**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:

**Hint**

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

**Answer**

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 .

## Comments