虚拟内存技术
memory
【问题描述】
操作系统对存储管理的处理中有一种很重要的技术，虚拟内存技术。操作系统中允许进程的同时运行，也就是并行。每个进程都有其相对独立的数据块（进程运行的过程当中将对其进行读写操作）。理想的情况下，这些数据块都应该是存放在内存当中的，这样才能够实现高效的读写操作。但事实上，内存的容量是有限的，每个进程只可能把一部分数据放在内存当中，为了解决这个矛盾，提出了虚拟内存技术。
虚拟内存技术的基本原理是：对进程而言，内存空间是无限大的，进程可以随意的读写数据，而对操作系统内部而言，利用外存来模拟扩充内存空间，进程要求访问某一个内存单元，交由操作系统处理，操作系统首先在内存中查找该单元是否存在，如果存在，查找成功，否则转入外存查找（一定是存在于外存当中的）。
对于存储介质的物理性质而言，内存的访问速度相对于外存而言是快得多的，因此对于每个进程而言操作系统应该把那些访问次数较多的数据存放在内存当中，而那些访问次数很少的则放在外存当中。如何选择内存中暂留的数据是一个很值得研究的问题，下面介绍一个处理内存管理比较常用的算法：
内存中的数据以页为基本存储单位，进程的读写操作都是针对页进行的。实际内存空间被分割成n页，虚拟内存空间的页数往往要大得多。某一时刻，进程需要访问虚存编号为P的页，该算法的执行步骤于下：
a. 首先在内存中查找，如果该页位于内存当中，查找成功，转d，否则继续下面的操作；
b. 寻找内存中是否存在空页（即没有装载任何数据页的页面），如果有，从外存中读入要查找页，并将该页送至内存中的空页进行存储，转d，否则继续下面的操作
c. 在内存中寻找一个访问次数最少的页面（如果存在多个页面，选取最早读入数据进入内存的那个页面），从外存中读入要查找页，替换该页。
d. 结束
注释：所谓访问次数指当前页面从进入内存到该时刻被访问的次数，如果该页面以前进入过内存并被其它页面替换，前面的访问次数不应该计如这个时刻的访问次数当中
你的任务是设计一个程序实现上述算法。
测试数据将会提供m条读写内存的命令，每条命题提供要求访问的虚拟内存页的编号P。你的程序要求能够模拟整个m条命令的全部执行过程.，所有的命令是按照输入的先后执行的，最开始的时候内存中的n页都是空的。
【输入】
输入文件的第一行为n<10000，m<1000000，接下来的m行每行有一个正整数Pi<=10^9，表示每一条指令需要访问的虚拟内存页的编号。
【输出】
输出文件仅有一个正整数，表示在整个的模拟过程当中，在内存当中直接查找成功的次数（即上面的算法只执行步骤a）。
【输入输出示例】
输入input.txt 输出Output.txt
3 811234254 1
【示例说明】
输入页编号 1 1 2 3 4 2 5 4
内存页面1 1 1 1 1 1 1 1 1
内存页面2 空 空 2 2 4 4 5 5
内存页面3 空 空 空 3 3 2 2 4
查找成功 失败 成功 失败 失败 失败 失败 失败 失败
