Polish version    English version  
  History of OI -> XII OI 2004/2005 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
Regulations
For contestants
Helpful resources
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN

Task: sam

Toy Cars

I stage competition  
Source file: sam.xxx (xxx=pas,c,cpp)
Memory limit: 32 MB

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 there are three integers: n, k, p (1 <= k <= n <= 100.000, 1 <= p <= 500.000), 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

In the first and only line of the standard output one integer should be written - the minimal number of times his mother has to pick a car from the shelf.

Example

For the following input data:

3 2 7
1
2
3
1
3
1
2

the correct answer is:

4



Print friendly version