#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 Heap3 {
	private:
		int array[1100000];
		int count;

	public:
		Heap3();

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

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

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

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

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

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

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

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

int Heap3::top() const {
	return array[0];
}

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

	// Percolate up

	while ( posn > 0 ) {
		int parent = (posn - 1)/3;

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

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

		posn = parent;
	}
}

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

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

	int posn = 0;
	int posn3 = 0;
	int child1 = 1;
	int child2 = 2;
	int child3 = 3;

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

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

		posn3 = 3*posn;
		child1 = posn3 + 1;
		child2 = posn3 + 2;
		child3 = posn3 + 3;
	}

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

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

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