Railway Transportation

ACM has produced a new series of enormous billboards that must be shipped by train. The billboards are loaded onto carriages, but the carriages reach the sorting station in a jumbled order, while ACM needs them delivered in a specific order.

The station has $M$ parallel tracks. The carriages approach one at a time, and each carriage may be sent onto any one of the tracks. Once a carriage is on a track it can only move forward — it can never back up. At the far end all tracks merge into a single outgoing rail, where again carriages can only move forward. Because a carriage can never reverse, the carriages on any single track leave that track in exactly the same order in which they entered it.

We want the carriages to leave the station in nondescending order of their target numbers. The carriages approach in the order given in the input, and the $i$-th number is the target value of the $i$-th arriving carriage. Carriages that share the same number may leave in any relative order. The tracks are long enough to hold any number of carriages.

The input consists of several scenarios. Each scenario is described on two lines, and the end of the input is signalled by a line containing two zeros.

The first line of a scenario contains two integers $N$ and $M$ separated by a space, where $1 \le N \le 200000$ and $1 \le M \le 200000$: $N$ is the number of carriages and $M$ is the number of tracks.

The second line contains $N$ nonnegative integers — the target values of the carriages, listed in the order in which they arrive. Some values may be equal; in that case the relative order of those carriages does not matter.

For each scenario, print a single line.

Every track releases its carriages in the same order they entered it, so the carriages assigned to one track must already be in nondescending order. The carriages can therefore be delivered in nondescending order using the $M$ tracks if and only if they can be split into at most $M$ groups that are each nondescending in arrival order.

Print the minimum number of tracks required to deliver every carriage in nondescending order. If that minimum is greater than $M$, the delivery is impossible with the available tracks; in that case print Transportation failed instead.