CACHE PART I

PYTHON PROGRAMMING LANGUAGE!!

PYTHON PROGRAMMING LANGUAGE!!

PYTHON PROGRAMMING LANGUAGE!!

(Before reading the following description, please read the introduction first.) In this problem, you need to implement a FIFO cache. When CPU needs to access data, the following steps are performed. 1. If the required data is stored in the cache, then a cache hit occurs; CPU can immediately access the data. Otherwise, a cache miss occurs. 2. If a cache miss occurs and the cache is full, we erase the data that is least recently stored into the cache. Then we copy the required data from main memory into the cache. Now we give an example. In this example, the capacity of the cache is 2, and we use a sequence to represent the addresses of data stored in the cache, where data least recently added is listed first. At first, the content of the cache is ) (the empty sequence). CPU accesses data as follows. 1. CPU accesses data at address 0. A cache miss occurs, now the content of cache is (0). 2. CPU accesses data at address 1. A cache miss occurs; now the content of cache is (0,1). 3. CPU accesses data at address 0. A cache hit occurs; the content of cache remains the same. 4. CPU accesses data at address 2. A cache miss occurs, now the content of cache is (1,2). 5. CPU accesses data at address 0. A cache miss occurs, now the content of cache is (2,0). 6. CPU accesses data at address 2. A cache hit occurs; the content of cache remains the same. Now given the sequence of addresses of data that CPU accesses, you are asked to count the number of cache misses (i.e, the number of times that accessed data does not occur in the cache). Input Format The first line contains two positive integers n and c, where n is the number of data accesses and c is the capacity of the cache. The second line contains the addresses 01, 02, ...,an of accessed data. Output Format Output the number of cache misses. Limits 1