#include<fstream>
using namespace std;

FILE *f1=fopen("schi.in","r");
FILE *f2=fopen("schi.out","w");

typedef struct nod_ABC *ptr_ABC;

struct nod_ABC
{
	int cheie;
	char pozitie;
	ptr_ABC st;
	ptr_ABC dr;
	char h;
};
ptr_ABC radacina;
	int n,i,x;
	ifstream fin ("schi.in");
	ofstream fout("schi.out");
inline short int inaltime (ptr_ABC rad)
{
	//if (!rad) return -1;
	return rad?rad->h:-1;
}
short int contor(ptr_ABC p)
{
	if(p->dr==NULL) return p->pozitie;
	return p->pozitie+contor(p->dr);
}
ptr_ABC rotatie_simpla_dreapta(ptr_ABC p2)
{
	ptr_ABC p1;
	p1=p2->st;
	p2->st=p1->dr;
	p1->dr=p2;
	short int poz= (p2->st?contor(p2->st):0);
	p2->pozitie=poz+1;
	p2->h=max(inaltime(p2->st), inaltime(p2->dr))+1;
	p1->h=max(inaltime(p1->st), inaltime(p2))+1;
	return p1;
}
/*ptr_ABC rotatie_simpla_dreapta(ptr_ABC p2)
{
	ptr_ABC p1;
	p1=p2->st;
	p2->st=p1->dr;
	p1->dr=p2;
	int poz= (p2->st?p2->st->pozitie:0);
	p2->pozitie=poz+1;
	p2->h=max(inaltime(p2->st), inaltime(p2->dr))+1;
	p1->h=max(inaltime(p1->st), inaltime(p2))+1;
	return p1;
}*/
ptr_ABC rotatie_simpla_stanga(ptr_ABC p1)
{
	ptr_ABC p2;
	p2=p1->dr;
	p1->dr=p2->st;
	p2->st=p1;
	p2->pozitie=contor(p1)+1;
	p1->h=max(inaltime(p1->st), inaltime(p1->dr))+1;
	p2->h=max(inaltime(p2->st), inaltime(p1))+1;
	return p2;
}
ptr_ABC rotatie_dubla_dreapta(ptr_ABC p3)
{
	
	p3->st=rotatie_simpla_stanga(p3->st);
	return rotatie_simpla_dreapta(p3);
	
}
ptr_ABC rotatie_dubla_stanga(ptr_ABC p1)
{
	
	p1->dr = rotatie_simpla_dreapta(p1 -> dr);
	return rotatie_simpla_stanga(p1);
	
}

ptr_ABC inserare_pozitie ( ptr_ABC p, int x, int nr)
{
	
	short int poz=nr;
	if(!p) 
	{
		p= new nod_ABC;
		p->cheie=x;
		p->pozitie=1;
		p->st=p->dr=NULL;
		p->h=0;
	}
	else 
		if(poz  <= p->pozitie) 
		{
			(p->pozitie)++;
			p ->st =inserare_pozitie(p->st,x,poz);
			if ( inaltime(p-> st) - inaltime(p->dr)==2)
				if (inaltime(p->st->st)>inaltime(p->st->dr))
					p=rotatie_simpla_dreapta(p);
				else
					p=rotatie_dubla_dreapta(p);
			else
				p->h=max(inaltime(p->st), inaltime(p->dr))+1;
		}
		else 
			if (poz > p->pozitie)
			{
				poz=poz-p->pozitie;
				p->dr=inserare_pozitie(p->dr,x,poz);
				if ( inaltime(p-> dr) - inaltime(p->st)==2)
					if ( inaltime(p->dr->dr) > inaltime(p->dr->st))
						p=rotatie_simpla_stanga(p);
					else
						p=rotatie_dubla_stanga(p);
				else
					p->h=max(inaltime(p->st), inaltime(p->dr))+1;	
			}
	return p;
}

void parcurgere_inordine( ptr_ABC p)
{
	if(p)
	{
		parcurgere_inordine(p->st);
		fprintf(f2,"%d\n", p->cheie); 
		parcurgere_inordine(p->dr);
	}

}
	
int main()
{
	fscanf(f1,"%d", &n); 
	for(i=1;i<=n;i++)
	{
		fscanf(f1,"%d", &x); 
		radacina=inserare_pozitie(radacina,i,x);
		
	}
	parcurgere_inordine(radacina);
	return 0;
}