SAM  Toy Cars
Jasio is a little boy  he is only three years old and enjoys playing with toy cars very much. Jasio has n different cars. They are kept on a shelf so high, that Jasio cannot reach it by himself. As there is little space in his room, at no moment may there be more than k toy cars on the floor. Jasio plays with one of the cars on the floor. Jasio's mother remains in the room with her son all the time. When Jasio wants to play with another car that is on the floor, he reaches it by himself. But when the toy is on the shelf, his mummy has to hand it to him. When she gives Jasio one car, she can at the same time pick any car from the floor and put it back on the shelf (so that there remains sufficient space on the floor). The mother knows her child very well and therefore can predict perfectly which cars Jasio will want to play with. Having this knowledge, she wants to minimize the number of times she has to hand Jasio a toy from the shelf. Keeping that in mind, she has to put the toys off on the shelf extremely thoughtfully.
Task
Write a programme that:
 reads from the standard input the sequence of toy cars in order in which Jasio will want to play with them,
 calculates the minimal number of times the mother has to pick cars from the shelf,
 writes the result to the standard output.
Input
In the first line of the standard input is H the number of test case (H <= 16). For each test case follow contains some lines, start with three integers: n, k, p (1 <= k <= n <= 100000, 1 <= p <= 500000), separated by single spaces. These denote respectively: the total number of cars, the number of cars that can remain on the floor at once and the length of the sequence of cars which Jasio will want to play with. Each of the following p lines contains one integer. These integers are the numbers of cars Jasio will want to play with (the cars are numbered from 1 to n ).
Output
For each test case, you should write only one integer  the minimal number of times his mother has to pick a car from the shelf.
Example
Input: 1 3 2 7 1 2 3 1 3 1 2 Output: 4
hide comments
vl4deee11:
20240701 18:09:15
cool task! thx! 

Rameshwar:
20160526 07:42:15
Please correct the sample input. You haven't written the number of testcases.


József Farkas:
20141122 21:24:14
I'm getting TLE. Could somebody give me the complexity of this problem? 

যোবায়ের:
20120808 20:40:08
what about H ?

Added by:  Hoang Hong Quan 
Date:  20060108 
Time limit:  1.075s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  12th Polish Olympiad in Informatics, stage 1 