#include<iostream>
#include<queue>

using namespace std;

int max(int a, int b)
{
	if (a >= b) return a;
	return b;
}

struct NOD
{
	int key;
	int factorBalansare;
	NOD* left;
	NOD* right;
	NOD* parent;
	NOD(int inf = 0)
	{
		key = inf;
		factorBalansare = 0;
		left = NULL;
		right = NULL;
		parent = NULL;

	}
};

struct AVL
{
	NOD* radacina;
	AVL()
	{
		radacina = NULL;
	}
	int height(NOD* x)
	{
		if (x == NULL)
			return 0;
		return (1 + max(height(x->left), height(x->right)));
	}
	/*void setBalance(NOD* x)
	{
		x->factorBalansare = height(x->right) - height(x->left);
	}*/
	void Insert(NOD* newNod)
	{
		NOD* nodParinte;
		nodParinte = NULL;
		NOD *x = radacina;
		while (x != NULL)
		{
			nodParinte = x;
			if (newNod->key < x->key)
				x = x->left;
			else
				x = x->right;
		}
		newNod->parent = nodParinte;
		if (nodParinte == NULL)
			radacina = newNod;
		else
		{
			if (newNod->key < nodParinte->key)
				nodParinte->left = newNod;
			else
				nodParinte->right = newNod;
			newNod->parent = nodParinte;
		}
		insert_repair(newNod);
	}
	void insert_repair( NOD* x)
	{
		BALANCE_FACTOR(x);
		if (x->factorBalansare == -2)
		{
			if (x->left->factorBalansare == 1)
				rotatieST(x->left);
			rotatieDR(x);

		}
		else
		{
			if (x->factorBalansare == 2)
			{
				if (x->right->factorBalansare == -1)
					rotatieDR(x->right);
				rotatieST(x);
			}
		}
		if (x->parent != NULL)
			insert_repair( x->parent);
	}
	void BALANCE_FACTOR(NOD* x)
	{
		int hst=1, hdr=1;
		if (x->left != NULL)
			hst = height(x->left);
		else
			hst = 0;

		if (x->right != NULL)
			hdr = height(x->right);
		else
			hdr = 0;

		x->factorBalansare = hdr - hst;
	}
	void transplant(NOD* u, NOD* v)
	{
		if (u->parent == NULL)
			radacina = v;
		else
		{
			if (u == u->parent->left)
				u->parent->left = v;
			else
				u->parent->right = v;
		}
		if (v != NULL)
			v->parent = u->parent;
	}
	void delete_repair(NOD* x)
	{
		BALANCE_FACTOR(x);
		if (x->factorBalansare == -2)
		{
			if (x->left->factorBalansare == -1 || x->left->factorBalansare == 0)
				rotatieDR(x);
			if (x->left->factorBalansare == 1)
			{
				rotatieST(x->left);
				rotatieDR(x);
			}
		}
		if (x->factorBalansare == 2)
		{
			if (x->right->factorBalansare == 1 || x->right->factorBalansare == 0)
				rotatieST(x);
			if (x->right->factorBalansare == -1)
			{
				rotatieDR(x->right);
				rotatieST(x);
			}
		}
		if (x->parent != NULL)
			delete_repair(x->parent);
	}
	void delete_AVL(NOD* z)
	{
		NOD* y;
		NOD* s = z->parent;
		if (z->left == NULL)
			transplant(z, z->right);
		else
			if (z->right == NULL)
				transplant(z, z->left);
			else
			{
				y = succesor(z);
				s = y->parent;
				if (y != z->right)
				{
					transplant(y, y->right);
					y->right = z->right;
					z->right->parent = y;
				}

				y->left = z->left;
				z->left->parent = y;
				transplant(z, y);
			}
		delete_repair(s);
		delete z;
	}
	NOD* min_AB(NOD*x)
	{
		NOD* y = x;
		while (y->left != NULL)
			y = y->left;
		return y;
	}

	NOD* max_AB(NOD*x)
	{
		NOD* y = x;
		while (y->right != NULL)
			y = y->right;
		return y;
	}

	NOD* succesor(NOD*x)
	{
		NOD* y;
		if (x->right != NULL)
		{
			y = min_AB(x->right);
			return y;
		}
		y = x->parent;
		while (y != NULL && x == y->right)
		{
			x = y;
			y = y->parent;
		}
		return y;
	}
	NOD* predecesor(NOD*x)
	{
		NOD* y;
		if (x->left != NULL)
		{
			y = max_AB(x->left);
			return y;
		}
		y = x->parent;
		while (y != NULL && x == y->left)
		{
			x = y;
			y = y->parent;
		}
		return y;
	}
	void rotatieST(NOD* y)
	{
		NOD*x = y->right;
		y->right = x->left;
		if (x->left != NULL)
			x->left->parent = y;
		x->parent = y->parent;
		if (y->parent == NULL)
			radacina = x;
		else
		{
			if (y == y->parent->left)
				y->parent->left = x;
			else
				y->parent->right = x;
		}
		x->left = y;
		y->parent = x;
	}

	void rotatieDR(NOD* y)
	{
		NOD*x = y->left;
		y->left = x->right;
		if (x->right != NULL)
			x->right->parent = y;
		x->parent = y->parent;
		if (y->parent == NULL)
			radacina = x;
		else
		{
			if (y == y->parent->right)
				y->parent->right = x;
			else
				y->parent->left = x;
		}
		x->right = y;
		y->parent = x;
	}
	void printPreorder(NOD* rad)
	{
		if (rad != NULL)
		{
			cout << rad->key << " ";
			printPreorder(rad->left);
			printPreorder(rad->right);
		}

	}
	void prntInorder(NOD* rad)
	{
		if (rad != NULL)
		{
			prntInorder(rad->left);
			cout << rad->key << " ";
			prntInorder(rad->right);
		}

	}
	void printPostorder(NOD* rad)
	{
		if (rad != NULL)
		{
			printPostorder(rad->left);
			printPostorder(rad->right);
			cout << rad->key << " ";
		}
	}
	void printLevel(NOD* x)
	{
		queue<NOD*> coada;
		coada.push(x);
		while (!coada.empty())
		{
			NOD *y = coada.front();
			cout << y->key << " ";
			if (y->left != NULL) coada.push(y->left);
			if (y->right != NULL) coada.push(y->right);
			coada.pop();
		}
	}

};

int main()
{
	int n,key;
	AVL a;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> key;
		NOD* nod = new NOD(key);
		a.Insert(nod);
	}
	a.printLevel(a.radacina);
	cout << endl;
	cin >> key;
	NOD* nod = new NOD(key);
	a.delete_AVL(nod);
	a.printLevel(a.radacina);
	system("pause");
	return 0;
}