/*
Un program care sa ordoneze o lista prin insertie
*/

#include<fstream.h>
#include<conio.h>

struct nod
       {int info;
	nod *urm;
       }*a;

void afis(nod *a)
       {
	for(a;a!=0;a=a->urm)
	   cout<<a->info<<" ";
	cout<<endl;
       }

main()
{clrscr();
 
 int n,i=0,cec;
 nod *e1,*e2,*b,*q;

 fstream f("L_OR_INS.txt",ios::in);

 f>>n;

 a=0;
 cec=-100//-1 si merge;
 b->info=cec;

 while(n)
     {n--;
      cec=0;
      if(a==0)
	{e1=new nod;
	 f>>e1->info;

	 e1->urm=a;
	 a=e1;
	}
     else
	{e2=new nod;
	 f>>e2->info;

	if(b->info<e1->info)
	  b=e1;

	 e1=a;

	 if(e1->info>e2->info)
	   {e2->urm=e1;
	    a=e2;
	    }
	   else
	     if(e2->info>b->info)
		{b->urm=e2;
		 e2->urm=0;
		 e1=e2;
		}
	      else
		{while(e1->urm&&cec==0)
		     {if(e2->info>e1->info&&e2->info<e1->urm->info)
			{q=e1->urm;
			 e1->urm=e2;
			 e2->urm=q;
			 cec=1;
			}
			e1=e1->urm;
		     }
	 }


	}

     }

 afis(a);

getch();
}