#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>

using namespace std;


int maxdis(int *dis,int max)
{
	int m=0;
	for(int i=0;i<max;i++)
	{
		if(dis[i]>dis[m]) m=i;
	}	
	return(m);
}

int found(int x,int *l,int j)
{
	for(int i=0;i<j;i++)
		if(l[i]==x){return(i);}
	return(-1);
}

int found1(int x,int *temp,int max)
{
	for(int i=0;i<max;i++)
		if(temp[i]==x) return(i);
	return(-1);
}

int main()
{
	cout<<"\n\nEnter the maximum number of frames in the main memory:\t";
	int max;
	cin>>max;
	int *temp=new int[max];
	int *dis=new int[max];
	int *flag=new int[max];
	for(int i=0;i<max;i++) flag[i]=0;
	cout<<"\n\nEnter the total number of page requests:\t";
	int n,res;
	cin>>n;
	
	cout<<"\n\nEnter the entire sequence of page requests:\t";
	int *a=new int[n];
	for(int i=0;i<n;i++) a[i]=-1;
	for(int i=0;i<n;i++) cin>>a[i];
	
	cout<<"\n\nprocess pages are then allocated as follows:\n\n";
	int j=0;
	for(int i=0;i<max;)
	{
		cout<<"\n\npage "<<a[j]<<" has been allocated frame "<<i<<" in MM";
		if((res=found(a[j],temp,i))!=-1) {cout<<"\n\npage "<<a[j]<<" already exists in frame "<<res<<" in MM";j++;}
		else {j++;temp[i++]=a[i];}
	}
	
	for(int i=j;i<n;i++)
	{
		for(int z=0;z<max;z++) flag[z]=0;
		if((res=found1(a[i],temp,max))!=-1) {cout<<"\n\npage already exists in frame "<<res<<" in MM";continue;}
		
		cout<<"\n\npage fault has occured";
		
		for(int x=0;x<max;x++)
			for(int y=i+1;y<n;y++)
			{
				if(temp[x]==a[y] && flag[x]==0) {dis[x]=y;flag[x]=1;}
				else if(flag[x]!=1) dis[x]=1000000;
			}
		
		
		int pos=maxdis(dis,max);
		cout<<"\n\npage "<<a[i]<<" has been allocated frame "<<pos<<" in MM by replacing page "<<temp[pos];
		temp[pos]=a[i];
		
	}
	
	delete[] temp;
	delete[] dis;
	delete[] flag;
	delete[] a;
	
	return(0);
}