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

	public:
		Heap5();

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

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

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

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

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

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

	// Percolate up

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

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

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

		posn = parent;
	}
}

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

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

	int posn = 0;
	int posn5 = 0;
	int child1 = 1;
	int child2 = 2;
	int child3 = 3;
	int child4 = 4;
	int child5 = 5;

	while ( child5 < 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] ) {
						if ( array[child5] < array[child4] ) {
							array[posn] = array[child5];
							posn = child5;
						} else {
							array[posn] = array[child4];
							posn = child4;
						}
					} else {
						if ( array[child5] < array[child3] ) {
							array[posn] = array[child5];
							posn = child5;
						} else {
							array[posn] = array[child3];
							posn = child3;
						}
					}
				} else {
					if ( array[child4] < array[child2] ) {
						if ( array[child5] < array[child4] ) {
							array[posn] = array[child5];
							posn = child5;
						} else {
							array[posn] = array[child4];
							posn = child4;
						}
					} else {
						if ( array[child5] < array[child2] ) {
							array[posn] = array[child5];
							posn = child5;
						} else {
							array[posn] = array[child2];
							posn = child2;
						}
					}
				}
			} else { 
				if ( array[child3] < array[child1] ) {
					if ( array[child4] < array[child3] ) {
						if ( array[child5] < array[child4] ) {
							array[posn] = array[child5];
							posn = child5;
						} else {
							array[posn] = array[child4];
							posn = child4;
						}
					} else {
						if ( array[child5] < array[child3] ) {
							array[posn] = array[child5];
							posn = child5;
						} else {
							array[posn] = array[child3];
							posn = child3;
						}
					}
				} else {
					if ( array[child4] < array[child1] ) {
						if ( array[child5] < array[child4] ) {
							array[posn] = array[child5];
							posn = child5;
						} else {
							array[posn] = array[child4];
							posn = child4;
						}
					} else {
						if ( array[child5] < array[child1] ) {
							array[posn] = array[child5];
							posn = child5;
						} else {
							array[posn] = array[child1];
							posn = child1;
						}
					}
				}
			}
		} else if ( array[child2] < last ) {
			if ( array[child3] < array[child2] ) {
				if ( array[child4] < array[child3] ) {
					if ( array[child5] < array[child4] ) {
						array[posn] = array[child5];
						posn = child5;
					} else {
						array[posn] = array[child4];
						posn = child4;
					}
				} else {
					if ( array[child5] < array[child3] ) {
						array[posn] = array[child5];
						posn = child5;
					} else {
						array[posn] = array[child3];
						posn = child3;
					}
				}
			} else {
				if ( array[child4] < array[child2] ) {
					if ( array[child5] < array[child4] ) {
						array[posn] = array[child5];
						posn = child5;
					} else {
						array[posn] = array[child4];
						posn = child4;
					}
				} else {
					if ( array[child5] < array[child2] ) {
						array[posn] = array[child5];
						posn = child5;
					} else {
						array[posn] = array[child2];
						posn = child2;
					}
				}
			}
		} else if ( array[child3] < last ) {
			if ( array[child4] < array[child3] ) {
				if ( array[child5] < array[child4] ) {
					array[posn] = array[child5];
					posn = child5;
				} else {
					array[posn] = array[child4];
					posn = child4;
				}
			} else {
				if ( array[child5] < array[child3] ) {
					array[posn] = array[child5];
					posn = child5;
				} else {
					array[posn] = array[child3];
					posn = child3;
				}
			}
		} else if ( array[child4] < last ) {
			if ( array[child5] < array[child4] ) {
				array[posn] = array[child5];
				posn = child5;
			} else {
				array[posn] = array[child4];
				posn = child4;
			}
		} else if ( array[child5] < last ) {
			array[posn] = array[child5];
			posn = child5;
		} else {
			array[posn] = last;
			return;
		}

		posn5 = 5*posn;
		child1 = posn5 + 1;
		child2 = posn5 + 2;
		child3 = posn5 + 3;
		child4 = posn5 + 4;
		child5 = posn5 + 5;
	}

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

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

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