#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

ofstream g("algsort.out",ofstream::out);

class Node {
	public:
		Node(int info,int index);
		int info,index;
		Node *left,*right;
		static Node* top;
};

Node::Node(int info,int index) {
	this->index = index;
	this->info = info;
	if (!top) top = this;
	left = NULL;
	right = NULL;
}

Node* Node::top = NULL;

void AddNode(Node* head,int info,int index) {
	if (info < head->info) {
		if (head->left) AddNode(head->left,info,index);
		else head->left = new Node(info,index);
	}
	else {
		if (head->right) AddNode(head->right,info,index);
		else head->right = new Node(info,index);
	}
}

int CheckHeight(Node* head) {
	if (!head) return 0;
	int left = CheckHeight(head->left);
	int right = CheckHeight(head->right);
	if (left > right) return 1 + left;
	else return 1 + right;
}

void BalanceRight(Node* head,Node* father) {
	if (CheckHeight(head->left->left) > CheckHeight(head->left->right)) {
		if (father)
			if (father->right == head) father->right = head->left;
			else father->left = head->left;
		else Node::top = head->left;
		Node* leftright = head->left->right;
		head->left->right = head;
		head->left = leftright;
	}
	else {
		if (father)
			if (father->right == head) father->right = head->left->right;
			else father->left = head->left->right;
		else Node::top = head->left->right;
		Node* leftright = head->left->right;
		head->left->right = leftright->left;
		leftright->left = head->left;
		head->left = leftright->right;
		leftright->right = head;
	}
}

void BalanceLeft(Node* head,Node* father) {
	if (CheckHeight(head->right->right) > CheckHeight(head->right->left)) {
		if (father)
			if (father->right == head) father->right = head->right;
			else father->left = head->right;
		else Node::top = head->right;
		Node* rightleft = head->right->left;
		head->right->left = head;
		head->right = rightleft;
	}
	else {
		if (father)
			if (father->right == head) father->right = head->right->left;
			else father->left = head->right->left;
		else Node::top = head->right->left;
		Node* rightleft = head->right->left;
		head->right->left = rightleft->right;
		rightleft->right = head->right;
		head->right = rightleft->left;
		rightleft->left = head;
	}
}

void CheckAVL(Node* head,Node* parent) {
	if (head->left) CheckAVL(head->left,head);
	if (head->right) CheckAVL(head->right,head);
	int leftTreeHeight = CheckHeight(head->left);
	int rightTreeHeight = CheckHeight(head->right);
	if (abs(leftTreeHeight - rightTreeHeight) > 1) {
		if (leftTreeHeight > rightTreeHeight) BalanceRight(head,parent);
		else BalanceLeft(head,parent);
	}
}

void SRD(Node* head) {
	if (!head) return;
	SRD(head->left);
	g<<head->info<<" ";
	SRD(head->right);
}

int main() {
	int n,x,i;
	ifstream f("algsort.in",ifstream::in);
	f>>n;
	int v[n];
	f>>x;
	Node* head = new Node(x,0);
	for (i=1;i<n;i++) {
		f>>x;
		AddNode(head,x,i);
		CheckAVL(head,NULL);	
		head = Node::top;
	}
	f.close();
	SRD(head);
	g.close();
	return 0;
}