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

typedef struct DuLNode{
	int data;
	int freq;
	struct DuLNode *prior;
	struct DuLNode *next;
}DuLNode,*DuLinkList;

void Locate(DuLinkList &L,int x)
{   	

	DuLinkList p,q;
	p=L;
	int k=1;

	while(x!=p->data)
	{   
		p=p->next;
		if(p==L) {k=0;break;}

	}
	
	

	if(k==0) {cout<<"not found!"<<endl;}

	else{
		p->freq++;
		
		   while(p->freq>p->prior->freq&&p!=L)
		   {  
		      
			  q=p->prior;
			  q->next=p->next;
			  p->prior=q->prior;
			  q->prior=p;
			  p->next=q;
			  q->next->prior=q;
			  p->prior->next=p;
			  if(p==L->prior)  break;
		   }
		   if(q==L) L=p;
		   
		  }

	
}




void main(void)
{    
    char ch='y';
	int num,k,x;
	int i;
	DuLinkList L,M,N;
	
	cout<<"please enter how many numbers there are in your list?"<<endl;
	cin>>num;
	
	cout<<"now please enter the "<<num<<" numbers in your list:"<<endl;
	L=(DuLNode *)malloc(sizeof(DuLNode));
	N=L;
	cin>>L->data;
	L->freq=0;
	

	for( i=0;i<num-1;i++)
	{  
		
		
	    M=(DuLNode *)malloc(sizeof(DuLNode));
	    cin>>k;
		M->data=k;
		M->freq=0;
	    N->next=M;		
		M->prior=N;      
		N=M;
		
		
				
	}
	M->next=L;
	L->prior=M;
	

	cout<<"the initial list is:"<<endl;
	M=L;
	cout<<L->data<<endl;
 	int numbe=0;
	while(numbe<num-1){
		M=M->next;
		cout<<M->data<<endl;
		numbe++;
		
	}

	while(ch=='y'||ch=='Y')
	{
			
	   cout<<"please enter the number you want to look up:"<<endl;
	   cin>>x;
       Locate(L,x);

	     cout<<"the new list is:"<<endl;
	     M=L;
	     cout<<L->data<<" "<<L->freq<<endl;
	     int number=0;
	  
	     while(number<num-1){
		  M=M->next;
		  cout<<M->data<<" "<<M->freq<<endl;
		  number++;
		 }
	   
		
	   

	     cout<<"do you please want to look up another number?"<<endl;
	     cout<<"if yes,enter 'y'; if no,enter 'n'."<<endl;
	     cin>>ch;
	}
	   
	   

	   


}