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

	public:
		Heap4();

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

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

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

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

void Heap4::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 Heap4::top() const {
	return array[0];
}

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

	// Percolate up

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

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

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

		posn = parent;
	}
}

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

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

	int posn = 0;
	int posn4 = 0;
	int child1 = 1;
	int child2 = 2;
	int child3 = 3;
	int child4 = 4;

	while ( child4 < count ) {
		// We will check if we have four children for this node;
		// else we will consider the cases of having 3, 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] ) {
					if ( array[child4] < array[child3] ) {
						array[posn] = array[child4];
						posn = child4;
					} else {
						array[posn] = array[child3];
						posn = child3;
					}
				} else if ( array[child4] < array[child2] ) {
					array[posn] = array[child4];
					posn = child4;
				} else {
					array[posn] = array[child2];
					posn = child2;
				}
			} else  if ( array[child3] < array[child1] ) {
				if ( array[child4] < array[child3] ) {
					array[posn] = array[child4];
					posn = child4;
				} else {
					array[posn] = array[child3];
					posn = child3;
				}
			} else if ( array[child4] < array[child1] ) {
				array[posn] = array[child4];
				posn = child4;
			} else {
				array[posn] = array[child1];
				posn = child1;
			}
		} else if ( array[child2] < last ) {
			if ( array[child3] < array[child2] ) {
				if ( array[child4] < array[child3] ) {
					array[posn] = array[child4];
					posn = child4;
				} else {
					array[posn] = array[child3];
					posn = child3;
				}
			} else if ( array[child4] < array[child2] ) {
				array[posn] = array[child4];
				posn = child4;
			} else {
				array[posn] = array[child2];
				posn = child2;
			}
		} else if ( array[child3] < last ) {
			if ( array[child4] < array[child3] ) {
				array[posn] = array[child4];
				posn = child4;
			} else {
				array[posn] = array[child3];
				posn = child3;
			}
		} else if ( array[child4] < last ) {
			array[posn] = array[child4];
			posn = child4;
		} else {
			array[posn] = last;
			return;
		}

		posn4 = 4*posn;
		child1 = posn4 + 1;
		child2 = posn4 + 2;
		child3 = posn4 + 3;
		child4 = posn4 + 4;
	}

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

			return;
		case 1:  // 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 2:  // One
			if ( array[child1] < last ) {
				array[posn] = array[child1];
				array[child1] = last;
			} else {
				array[posn] = last;
			}

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