#include <iostream>
#include <fstream>
#include <ctime>
#include <iomanip>
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");

struct node
{
	bool col;
	int key;
	node *st, *dr, *dad;

	node()
	{
		st = dr = dad = NULL;
		col = 0;
		key = 0;
		/// NEGRU = 0, ROSU = 1
	}
} *NIL;

void Del1(node*);
void Del2(node*);
void Del3(node*);
void Del4(node*);
void Del5(node*);
void Del6(node*);

node *root;
int sol = 1;

void RotLeft(node *x)
{
	if (x->dr == NIL)
		return;

	node *y = x->dr;
	node *aux1 = x->st, *aux2 = y->st, *aux3 = y->dr;
	if (x->dad == NIL)
		root = y;
	else
	{
		if (x->dad->st == x)
			x->dad->st = y;
		else
			x->dad->dr = y;
	}

	y->dad = x->dad;
	x->dr = y->st;
	if (x->dr != NIL)
		x->dr->dad = x;
	y->st = x;
	x->dad = y;
}

void RotRight(node *x)
{
	if (x->st == NIL)
		return;

	node *y = x->st;
	if (x->dad == NIL)
		root = y;
	else
	{
		if (x->dad->st == x)
			x->dad->st = y;
		else
			x->dad->dr = y;
	}

	y->dad = x->dad;
	x->st = y->dr;
	if (x->st != NIL)
		x->st->dad = x;
	y->dr = x;
	x->dad = y;
}

void InsertRepair(node *x)
{
	

	while (x->dad->col == 1)
	{
		
		node* grand = x->dad->dad;
		
		if (grand->st == x->dad)
		{
			if (grand->dr->col == 1)
			{
				x->dad->col = 0;
				grand->dr->col = 0;
				grand->col = 1;
				x = grand;
			}
			else
			{
				if (x->dad->dr == x)
				{
					x = x->dad;
					RotLeft(x);
				}
				x->dad->col = 0;
				grand->col = 1;
				RotRight(grand);
			}
		}
		else
		{
			
			if (grand->st->col == 1)
			{
				x->dad->col = 0;
				grand->st->col = 0;
				grand->col = 1;
				
			}
			else
			{
				if (x->dad->st == x)
				{
					x = x->dad;
					RotRight(x);
				}

				x->dad->col = 0;
				grand->col = 1;
				RotLeft(grand);
			}
		}
		x = grand;
	}

	root->col = 0;
}
void Insert(node *&root, int val)
{
	if (root == NULL)
	{
		root = new node;
		root->key = val;
		root->col = 0;
		root->dad = NIL;
		root->st = NIL;
		root->dr = NIL;
	}
	else
	{
		node *x = root, *aux = NIL;

		while (x != NIL)
		{
			aux = x;
			if (val <= x->key)
				x = x->st;
			else
				x = x->dr;
		}
		if (val <= aux->key)
		{
			aux->st = new node;
			aux->st->col = 1;
			aux->st->key = val;
			aux->st->dad = aux;
			aux->st->st = NIL;
			aux->st->dr = NIL;
			InsertRepair(aux->st);
		}
		else
		{
			aux->dr = new node;
			aux->dr->col = 1;
			aux->dr->key = val;
			aux->dr->dad = aux;
			aux->dr->dr = NIL;
			aux->dr->st = NIL;
			InsertRepair(aux->dr);
		}
	}
}

node* Search(node *root, int val)
{
	node *aux = root, *res = NIL;

	while (aux != NIL)
	{
		if (val < aux->key)
			aux = aux->st;
		else
			if (val > aux->key)
				aux = aux->dr;
			else
				return aux;
	}

	return NIL;
}

node* Succ(node *x)
{
	while (x->st != NIL)
		x = x->st;
	return x;
}
/*
void Delete(node* root, int val)
{
	node *x = Search(root, val);

	if (x->st == NIL && x->dr == NIL)
	{
		if (x->dad->st == x)
		{
			x->dad->st = NIL;
		}
		else
			x->dad->dr = NIL;
		delete x;
	}
	else
		if ((x->st == NIL) + (x->dr == NIL) == 1)
		{
			if (x->st == NIL)
			{
				x->key = x->dr->key;
				x->col = x->dr->col;
				node *aux = x->dr;
				
				x->st = x->dr->st;
				x->dr = x->dr->dr;

				x->st->dad = x;
				x->dr->dad = x;
				delete aux;
		
			}
			else
			{
				x->key = x->st->key;
				x->col = x->st->col;
				node *aux = x->st;

				x->dr = x->st->dr;
				x->st = x->st->st;
				
				x->st->dad = x;
				x->dr->dad = x;
				delete aux;
			
			}
		}
		else
		{
			node *aux = Succ(x->dr);
			int tmp = aux->key, tmp2 = aux->col;
			Delete(root, aux->key);
			x->key = tmp;
			x->col = tmp2;
		}
   
	
}

*/

node *sibling(node *x)
{
	if ((x == NIL) || (x->dad == NIL))
		return NULL;

	if (x == x->dad->st)
		return x->dad->dr;
	else
		return x->dad->st;
}

void Del1(node *x)
{
	if (x->dad == NIL)
		return;

	Del2(x);
}

void Del2(node *x)
{
	node *sib = sibling(x);
	if (sib != NULL && x->dad->col == 0 && sib->col == 1)
	{
		x->dad->col = 1;
		sib->col = 0;

		if (x->dad->st == x)
			RotLeft(x->dad);
		else
			RotRight(x->dad);
	}

	Del3(x);
}

void Del3(node *x)
{
	node *sib = sibling(x);

	if (sib != NULL && x->dad->col == 0 && sib->col == 0 && sib->st->col == 0 && sib->dr->col == 0)
	{
		sib->col = 1;
		Del1(x->dad);
	}
	else Del4(x);
}

void Del4(node *x)
{
	node *sib = sibling(x);
	if (sib != NULL && x->dad->col == 1 && sib->col == 0 && sib->st->col == 0 && sib->dr->col == 0)
	{
		x->dad->col = 0;
		sib->col = 1;
		return;
	}
	Del5(x);
}

void Del5(node *x)
{
	node *sib = sibling(x);

	if (sib->col == 0) {
		if ((x == x->dad->st) && (sib->dr->col == 0) && (sib->st->col == 1))
		{
			sib->col = 1;
			sib->st->col = 0;
			RotRight(sib);
		}
		else if ((x == x->dad->dr) && (sib->st->col == 0) && (sib->dr->col == 1))
		{
			sib->col = 1;
			sib->dr->col = 1;
			RotLeft(sib);
		}
	}
	Del6(x);
}

void Del6(node *x)
{
	node *sib = sibling(x);

	sib->col = x->dad->col;
	x->dad->col = 0;

	if (x == x->dad->st) {
		sib->dr->col = 0;
		RotLeft(x->dad);
	}
	else {
		sib->st->col = 0;
		RotRight(x->dad);
	}
}

void DelRepair(node *v, node *u)
{
	int ok = 0, nul = 0;

	if (v->col == 1 || u->col == 1)
		ok = 1;

	if (u != NIL)
	{
		cout << v->key << "\n\ns";
		v->key = u->key;
		v->col = u->col;
		v->st = u->st;
		v->dr = u->dr;

	    v->st->dad = v;
        v->dr->dad = v;
		delete u;
	}
	else
	{
		nul = 1;
		v->key = 0;
		v->col = 0;
		v->st = NULL;
		v->dr = NULL;
	}
	
	if (ok)
	{
		v->col = 0;
	}
	else
	{  
		Del1(v);
	}
	
	if (nul)
	{
		if (v->dad->st == v)
			v->dad->st = NIL;
		else
			v->dad->dr = NIL;

		delete v;
	}

}

void Delete(node* root, int val)
{
	node *x = Search(root, val);

	if (x->st == NIL && x->dr == NIL)
	{
		
		DelRepair(x, x->st);
	}
	else
		if ((x->st == NIL) ^ (x->dr == NIL))
		{
			if (x->st == NIL)
			{
				DelRepair(x, x->dr);
			}
			else
			{
				DelRepair(x, x->st);
			}
		}
		else
		{
		    node *aux = Succ(x->dr);
			int tmp = aux->key, tmp2 = aux->col;
			Delete(root, aux->key);
			x->key = tmp;
		}

}

void DFS(node *root)
{
	if (root->st != NIL)
		DFS(root->st);

	g << root->key << " "; 

	if (root->dr != NIL)
		DFS(root->dr);
}

int DFS2(node *root)
{
	int n1 = 0, n2 = 0;
	

	if (root->col == 1)
	{
		if (root->st->col == 1 || root->dr->col == 1)
		{
			sol = 0;
			//cout << "hello";
		}
	}
	if (root->st != NIL)
		n1 = DFS2(root->st);

	if (root->dr != NIL)
		n2 = DFS2(root->dr);
   
	if (n1 != n2) sol = 0;
	return n1 + (root->col == 0);
}

int main()
{
	int n, i, x;
	NIL = new node;

	srand(time(NULL));
	f >> n;

	for (i = 1; i <= n; i++)
	{
		f >> x;
		Insert(root, x);
	}
	


  DFS(root);
 // DFS2(root);
 // cout << "\n\n" << sol;

	//system("pause");
	return 0;
}