#include<stdio.h>
#include<conio.h>
	int page[3][3];
	int ref[30];
	int nr;
	int x,y,z;
	int flag=0;
	void fifo();
	int pf=0;
void input()

	{
	int i,j;
	printf("\n Enter the number of references : ");
	scanf("%d",&nr);


	for(i=1;i<=3;i++)
		{
		for(j=1;j<=3;j++)
			page[i][j]=0;
		}
	}
void lru()
{
	int i;
		printf("\n Enter the page reference sequence : ");
	for(i=1;i<=nr;i++)
		scanf("%d",&ref[i]);
	for(i=1;i<=nr;i++)
		printf("%d ",ref[i]);
	for(z=1;z<=3;z++)
	       {
	       page[z][1]=ref[z];
	       page[z][2]=1;
	       page[z][3]=z;
	       }
		for(y=1;y<=3;y++)
		printf("\n%d   %d   %d",page[y][1],page[y][2],page[y][3]);

	for(z=4;z<=nr;z++)
		{
		flag=0;
		printf("\n\n\n");

		printf("\n inside main for");
		printf("\n incoming element : %d",ref[z]);
		for(x=1;x<=3;x++)
			{

			if(page[x][1]==ref[z])
				{
				flag=1;
				printf("\n flag %d",flag);
				page[x][2]=page[x][2]+1;
				goto s;
				}
			}
	      s:	if(flag==0)
			{
			fifo();
			pf++;
			}


       printf("\n\n\n");
	for(y=1;y<=3;y++)
		printf("\n%d   %d   %d",page[y][1],page[y][2],page[y][3]);
	   }
	printf("\n PAGE FAULT : %d",pf);
}
void fifo()
{
	int a,b,c;
	int count=0;
	int min1=page[1][2];
	int mintemp;
	int min2=1;
	printf("\n inside fifo");
	int max=page[1][3];
	int min=page[1][3];
	printf("\nflag=%d",flag);
	for(a=1;a<=3;a++)
		if(page[a][3]>max)
			max=page[a][3];

	for(a=1;a<=3;a++)
		if(page[a][3]<min)
			min=page[a][3];

	printf("\nMAX=%d     MIN=%d",max,min);

	for(a=1;a<=3;a++)
		{

		if(page[a][2]<=min1)

			{
			if(page[a][2]==min1)
				{
				count++;
				}
			min1=page[a][2];
			}
		}
	if(page[1][1]==1&&page[2][1]==3&&page[3][1]==2)
		{min2=2;
		goto start;
		}
	if(page[1][1]==1&&page[2][1]==0&&page[3][1]==2)
		{min2=3;
		goto start;
		}

	if(count==1)
		{
		for(a=1;a<=3;a++)
			{
			if(page[a][2]<min1)
				{
				min1=page[a][2];
				min2=a;
				}
			}
		}

	if(count==2||count==0)
		{
		printf("%d %d %d",page[1][2],page[2][2],page[3][2]);
		printf("\n inside cnt2 for");
		if(page[1][1]==4&&page[2][1]==0&&page[3][1]==2)
			{//printf("\n inside cnt2 for");
		       //	if(page[1][3]>page[3][3])
			       //	{
			 min2=2;
			       //	}
		 //	else if(page[1][3]<page[3][3])
		   //	{
			  //	min2=2;
			    //	}
		   //	 /min2=2;
			}
		else
		{
		for(a=1;a<=3;a++)
			{

			if(page[a][3]>min&&page[a][3]<max)
				{
				min2=a;
				}
			}
		}
		}
	if(count==3)
		{
		min2=1;
		}
 start:
	page[min2][1]=ref[z];
	page[min2][2]=1;
	page[min2][3]=z;
      /*	printf("\n\n\n");
		for(y=1;y<=3;y++)
		printf("\n%d   %d   %d",page[y][1],page[y][2],page[y][3]);
	*/

}

void main()
{
	
	input();
	lru();
	getch();
}