A parking center by the Great Wall has a long row of parking places. One end of the row is considered left and the other end is considered right. The row is full of cars. Each car has a type and several cars may be of the same type. The types are identified by integer values. A number of workers decide to order the cars parked in the row in ascending order from left to right by the car types using the following method. In what is called a round, each of the workers can simultaneously drive one car out of its place and then park it in a place from where a car has been moved out in the same round. It may be that some workers are not moving a car in a round. For efficiency, a small number of rounds is preferable.
Suppose that N is the number of cars and W is the
number of workers. You are to write a program which, given the types of the
parked cars and the number of workers, finds such a way to sort the cars that
the number of rounds needed is at most , that is N/(W-1) rounded up. The minimal
number of rounds is never greater than .
Consider the following example. There are 10 parked cars of types 1,2,3, and 4 with 4 workers. The initial placement of the cars from left to right identified by their types is
2 3 3 4 4 2 1 1 3 1.
The minimal number of rounds is three, and the rounds can be implemented so that the placement after each round is as follows:
2 1 1 4 4 2 3 3 3 1 - after round 1,
2 1 1 2 4 3 3 3 4 1 - after round 2, and
1 1 1 2 2 3 3 3 4 4 - after round 3.
The input file name is CAR.IN. The first line in the input file contains three integers. The first integer is the number of cars N, 2<=N<=20000. The second integer is the number of types M, 2<=M<=50. The car types are identified by the integers from 1 to M. There is at least one car of each type. The third integer is the number of workers W, 2<=W<=M. The second line contains N integers, where the ith integer is the type of the ith car in the row, starting from the left end of the row.
The output file name is CAR.OUT. The first line of the output file contains one integer R, which is the number of rounds in the solution.
EXAMPLE INPUT AND OUTPUT
10 4 4 2 3 3 4 4 2 1 1 3 1