#include <iostream>

// This is a very quick-and-dirty implementation of a ternary min heap.
// It is designed to try to get the optimal implementation speed at the cost of clarity.

class Heap2opt {
	private:
		int array[1100000];
		int count;

	public:
		Heap2opt();

		int size() const;
		int top() const;
		void print() const;

		void push( int const );
		void pop();
};

Heap2opt::Heap2opt():count(0) {
	// emtpy
}

int Heap2opt::size() const {
	return count;
}

void Heap2opt::print() const {
	if ( size() == 0 ) {
		std::cout << 0 << ":" << std::endl;
		return;
	}

	std::cout << size() << ":  " << array[1];

	for ( int i = 2; i <= size(); ++i ) {
		std::cout << "-" << array[i];
	}

	std::cout << std::endl;
}

int Heap2opt::top() const {
	return array[1];
}

void Heap2opt::push( int const n ) {
	++count;
	array[count] = n;
	int posn = count;

	// Percolate up

	while ( posn > 1 ) {
		int parent = posn >> 1;

		if ( array[posn] >= array[parent] ) {
			return;
		}

		std::swap( array[posn], array[parent] );

		posn = parent;
	}
}

void Heap2opt::pop() {
	if ( count == 0 ) {
		return;
	}

	int last = array[count];
	--count;

	int posn = 1;
	int child1 = 2;
	int child2 = 3;

	while ( child2 <= count ) {
		// We will check if we have two children for this node;
		// else we will consider the cases of having 1 and 0 children.
		// In all later cases, we return.

		if ( array[child1] < last ) {
			if ( array[child2] < array[child1] ) {
				array[posn] = array[child2];
				posn = child2;
			} else { 
				array[posn] = array[child1];
				posn = child1;
			}
		} else if ( array[child2] < last ) {
			array[posn] = array[child2];
			posn = child2;
		} else {
			array[posn] = last;
			return;
		}

		child1 = posn << 1;
		child2 = child1 | 1;
	}

	switch ( child2 - count ) {
		case 1:  // One
			if ( array[child1] < last ) {
				array[posn] = array[child1];
				array[child1] = last;
			} else {
				array[posn] = last;
			}

			return;
		default:
			array[posn] = last;
	}
}