Description

Virtual memory is an important storage management technique in operating systems. Operating systems allow processes to run at the same time, i.e., in parallel. Each process has its own relatively independent block of data (which is read and written during execution). Ideally, all these data blocks should be in memory to support efficient read and write operations. In reality, memory capacity is limited, and each process can only keep part of its data in memory. To address this, virtual memory was introduced.

The basic idea of virtual memory is: from the process’s point of view, the memory space is unlimited, and the process can read and write data freely. Internally, the OS uses external storage to simulate an expanded memory space. When a process requests access to some memory unit, the OS handles it: it first checks whether the unit exists in memory. If it is found, the lookup succeeds; otherwise, it switches to external storage to find it (it certainly exists there).

Since memory is much faster than external storage, the OS should keep frequently accessed data in memory and place infrequently accessed data on external storage. How to choose which data remains in memory is worth studying. Below is a commonly used algorithm in memory management:

Data in memory is managed in units of pages, and read/write operations are performed on pages. The physical memory is divided into $n$ pages, while the number of pages in virtual memory is usually much larger. At some moment, when a process needs to access the virtual page with number $P$, the algorithm proceeds as follows:

a. First, look it up in memory. If the page is in memory, the lookup succeeds; go to d. Otherwise, continue with the steps below.

b. Check whether there is a free page frame in memory (i.e., a frame that does not store any data page). If there is, read the requested page from external storage and place it into the free frame in memory, then go to d. Otherwise, continue with the next step.

c. In memory, find a page with the least number of accesses (if multiple pages tie for the minimum, choose the one that was loaded into memory the earliest), then read the requested page from external storage and replace that page.

d. End.

The access count of a page is the number of times it has been accessed since it was loaded into memory this time. If the page had been in memory before and was evicted, its previous access count must not be counted for the current stay.

Your task is to implement the above algorithm.

The testdata will provide $m$ memory access commands. Each command gives the virtual page number $P$ to be accessed. Your program must simulate the entire execution of all $m$ commands in input order. Initially, all $n$ memory pages are empty.

Description

Input Format

There are $m + 1$ lines of input.
The first line contains $n$ and $m$ ($n \le 10000$, $m \le 1000000$), the number of memory page frames and the number of memory access commands, respectively.
Each of the next $m$ lines contains a positive integer $P_i$ ($P_i \le 10^9$), the virtual page number to be accessed by the $i$-th command (the $(i + 1)$-th line).

Output Format

Output a single integer: the number of times the page was found directly in memory during the simulation (i.e., the number of requests for which the algorithm executed only step a).

3 8 
1
1
2
3
4
2
5
4

1

Hint

Translated by ChatGPT 5