#include <iostream>

using namespace std ;

struct heap {
	int size ;
	int vector [1000] ;
};

void  citire_heap (heap &a)
{
	cin >> a.size ;
	for(int i = 1 ; i <= a.size ; i++)
		cin >> a.vector[i];
}

void max_heapify (heap &a , int i)
{
	if(i >= (a.size)/2 + 1)
		return ;
	if(a.vector[2 * i] >= a.vector [2 * i + 1] && a.vector[2 * i] > a.vector[i])
	{
		int aux = a.vector[2 * i] ;
		a.vector[2 * i] = a.vector[i];
		a.vector[i] = aux ;
		 max_heapify(a , 2 * i) ;
	}

	if(a.vector[2 * i + 1] >= a.vector [2 * i] && a.vector[2 * i + 1] > a.vector[i])
	{
		int aux = a.vector[2 * i + 1] ;
		a.vector[2 * i + 1] = a.vector[i];
	        a.vector[i] = aux ;
		max_heapify(a , 2 * i + 1) ;
	}

	return ;
}

void make_max_heap (heap &a)
{
	for(int i = a.size /2 ; i >= 1  ; i --)
		 max_heapify(a , i);
	return ;
}

int get_max(heap a)
{
	return a.vector[1] ;
}

int extract_max (heap & a)
{
	int rezultat = a.vector[1] ;
	a.vector[1] = a.vector[a.size --];
	max_heapify(a , 1);
	return rezultat ;
}

void insert_max_heap(heap &a , int x)
{
	a.size ++;
	a.vector[a.size] = x ;
	int i = a.size ;
	while (i > 1 && a.vector[i] > a.vector[i/2])
	{
		int aux = a.vector[i/2] ;
		a.vector[i/2] = a.vector[i] ;
		a.vector[i] = aux;
		i = i/2 ;
	}
}

void afisare_heap (heap &a)
{
	for(int i = 1 ; i <= a.size ; i ++)
		cout << a.vector[i] << " " ;
	cout << '\n' ;
}

int main()
{
	heap a ;
	citire_heap(a);
	make_max_heap (a);
	afisare_heap (a);
	int m = extract_max(a);
	cout << m << "   ";
	afisare_heap(a);
	insert_max_heap(a , 100);
	afisare_heap(a);
	return 0;
}