// Include
#include <fstream>
using namespace std;

// Structuri
enum type_color {undef=0, red, black};
struct type_node
{
	int value;
	type_color color;
	
	type_node *leftSon, *rightSon;
	type_node *father;
	
	type_node()
	{
		value = 0;
		color = red;
		
		leftSon = rightSon = '\0';
		father = '\0';
	}
};

// Functii
void insert(type_node *node, int value);

void redBlackTreeCheck(type_node *node);
type_node* getUncle(type_node *node);
bool isLeftSon(type_node *node);

void fix1(type_node *node, type_node *uncle);
void fix2(type_node *node, type_node *uncle, bool isLeftNode);
void fix3(type_node *node, type_node *uncle, bool isLeftNode);

void leftRotate(type_node *node1);
void rightRotate(type_node *node1);

void print(type_node *node);

// Variabile
ifstream in("rbt.in");
ofstream out("rbt.out");

int nodes;
int value;

type_node *root = new type_node;

// Main
int main()
{
	in >> nodes;
	
	in >> value;
	root->value = value;
	root->color = black;
	
	for(int i=2 ; i<=nodes ; ++i)
	{
		in >> value;
		insert(root, value);
	}
	
	print(root);
	
	in.close();
	out.close();
	return 0;
}

void insert(type_node *node, int value)
{
	/*if(value == node->value)
		return;*/
	
	if(value <= node->value)
	{
		if(node->leftSon)
			insert(node->leftSon, value);
		else
		{
			node->leftSon = new type_node;
			node->leftSon->father = node;
			node->leftSon->value = value;
			redBlackTreeCheck(node->leftSon);
		}
	}
	else
	{
		if(node->rightSon)
			insert(node->rightSon, value);
		else
		{
			node->rightSon = new type_node;
			node->rightSon->father = node;
			node->rightSon->value = value;
			redBlackTreeCheck(node->rightSon);
		}
	}
}

void redBlackTreeCheck(type_node *node)
{
	if(node->father->color == black) // Nu sunt probleme
		return;
	
	type_node *uncle = getUncle(node);
	
	if(!uncle || uncle->color == red)
		fix1(node, uncle);
	else
	{
		bool isLeftNode = isLeftSon(node);
		bool isLeftUncle = isLeftSon(uncle);
		
		if(isLeftNode ^ isLeftUncle) // Sunt pe parti opuse, doar cazul 2
			fix2(node, uncle, isLeftNode);
		else
			fix3(node, uncle, isLeftNode);
	}
}

type_node *getUncle(type_node *node)
{
	node = node->father;
	
	//#warning Sa nu uit de ; ala
	if(isLeftSon(node))//;
		return node->father->rightSon;
	
	return node->father->leftSon;
}

void fix1(type_node *node, type_node *uncle)
{
	node->father->color = black;
	
	if(uncle)
		uncle->color = black;
	
	node = node->father->father;
	
	if(node != root)
	{
		node->color = red;
		redBlackTreeCheck(node);
	}
}

void leftRotate(type_node *node1)
{
	type_node *node2 = node1->father;
	
	if(node2 != root)
	{
		if(isLeftSon(node2))
			node2->father->leftSon = node1;
		else
			node2->father->rightSon = node1;
	}
	else
		root = node1;
	
	node1->father = node2->father;
	
	node2->rightSon = node1->leftSon;
	if(node1->leftSon)
		node1->leftSon->father = node2;
	
	node1->leftSon = node2;
	node2->father = node1;
}

void rightRotate(type_node *node1)
{
	type_node *node2 = node1->father;
	
	if(node2 != root)
	{
		if(isLeftSon(node2))
			node2->father->leftSon = node1;
		else
			node2->father->rightSon = node1;
	}
	else
		root = node1;
	
	node1->father = node2->father;
	
	node2->leftSon = node1->rightSon;
	if(node1->rightSon)
		node1->rightSon->father = node2;
	
	node1->rightSon = node2;
	node2->father = node1;
}

bool isLeftSon(type_node *node)
{
	return node->father->leftSon == node;
}

void fix2(type_node *node, type_node *uncle, bool isLeftNode)
{
	if(isLeftNode)
		rightRotate(node->father);
	else
		leftRotate(node->father);
	
	node->father->color = black;
	uncle->color = black;
	uncle->father->color = red;
}

void fix3(type_node *node, type_node *uncle, bool isLeftNode)
{
	if(isLeftNode)
	{
		rightRotate(node);
		fix2(node->rightSon, uncle, isLeftSon(node->rightSon));
	}
	else
	{
		leftRotate(node);
		fix2(node->leftSon, uncle, isLeftSon(node->leftSon));
	}
	
}


void print(type_node *node)
{
	if(node->leftSon)
		print(node->leftSon);
	
	out << node->value << ' ';
	
	if(node->rightSon)
		print(node->rightSon);
}