#include<iostream>
#include<string>
#include<vector>

template<class T>
class opt{
	T v_;
	bool b;
public:

	template<class X = T >
	opt(X&&when_true,bool cond)noexcept 
		:b{cond},
		v_{ cond ? std::forward<X>(when_true) : T{} }
	{}
	

	explicit operator bool()const noexcept{
		return b;
	}

	explicit operator T()const& noexcept{
		return v_;
	}
	explicit operator T() & noexcept{
		return v_;
	}
	explicit operator T() && noexcept{
		return v_;
	}

	auto& operator *()const& noexcept{
		return v_;
	}
	auto& operator *()& noexcept {
		return v_;
	}
	auto& operator *() && noexcept {
		return v_;
	}

	friend auto
		operator <<(std::ostream& os, const opt& op)->std::ostream& {
		return
			os << (op ? 'T' : 'F') << ":" << (*op) ;
	}

};




template<class T>
auto make_opt(bool b,  T&& when_true) {

	return 
		opt<std::decay_t<T>>{ std::forward<T>(when_true),b};
}



using sll = signed long long;

template<class T>
auto left(const std::vector<T>& tab, int index) {
	const auto l_index = index * 2 + 1;
	const auto b = static_cast< decltype( tab.size() ) >
		(l_index) < tab.size();

	return
		make_opt(b, l_index);
}

template<class T>
auto right(const std::vector<T>& tab, int index) {
	const auto r_index = (index + 1 ) * 2;
	const auto b = static_cast<decltype( tab.size() )>
		(r_index) < tab.size();

	return
		make_opt(b, r_index );
}

template<class T>
auto parent(const std::vector<T>& tab, int index) {
	const auto p_index = 0 < index ? (index -1)/ 2 : index;
	const auto b = index != p_index;
//	std::cout << "opt:"<< make_opt(b, p_index, index)<<"\n";
	return
		make_opt(b, p_index);
}

template<class T>
auto max_heapify(std::vector<T>*const tp, int index)->int {
	auto& tab = *tp;

	auto lv = left(tab, index);
	auto max_index = lv && tab[index] < tab[*lv] ? *lv : index;

	auto rv = right(tab, index);
	max_index = rv && tab[max_index] < tab[*rv] ? *rv : max_index;

	/*
	std::cout
		<< "  mh:" << max_index << " " << index 
		<< " " << lv << " " << rv << ", "
		<< "max = " << tab[max_index] << ", "
		<< "tab[i] = " << tab[index] << ", ";

	(lv ? std::cout << "tab[L] = " << tab[*lv] : std::cout << "L-none") << ", ";
	(rv ? std::cout << "tab[R] = " << tab[*rv] : std::cout << "R-none") ;
	std::cout << "\n\n";
	*/

	if (max_index != index) {
		std::swap(tab[max_index], tab[index]);
		return 
			max_heapify(tp, max_index);
	}
	else {
		return index;
	}
}


template<class T>
auto insert(std::vector<T>*const tp, T&& elem) {
	auto& tab = *tp;

	tp->emplace_back( std::forward<T>(elem) );

	auto par = parent(tab, tab.size() - 1);
	
	/*
	std::cout
		<< "  insert : " << elem
		<< " size: " << tab.size()
		<< " parent:";
	
	if (par)
		std::cout << *par;
	else
		std::cout << "None";
	std::cout << "\n\n";
	*/
	while (par) {
		auto index = max_heapify(tp, *par);
		par = parent(tab, index);
	}
}

/*
template<class T>
auto insert(std::vector<T>*const tp, const T& elem) {
	auto& tab = *tp;

	std::cout << "insert : " << elem << "\n";

	tp->emplace_back(elem);
	auto par = parent(tab, tab.size() - 1);

	std::cout << par << "\n";
	if (par)
		max_heapify(tp, *par);
}*/

template<class T>
auto pop_max(std::vector<T>* const tp) {
	auto&tab = *tp;
	
	std::swap(tab.front(), tab.back());
	auto&& max_value = tab.back(); tab.pop_back();


	//for (auto i{tab.size()/2};i>0;--i)//
	//	max_heapify(tp, i-1);

	auto par = parent(tab, tab.size() - 1);

	while (par) {
		auto index = max_heapify(tp, *par);
		par = parent(tab, index);
	}

	return
		std::move(max_value);
}


int main() {
	std::vector<sll> tab;

	auto p = [&]() {
		for (const auto&e : tab)
			std::cout << " " << e;
		std::cout << "\n\n\n";
	};


	std::string s{};


	while (s != "end") {

		std::cin >> s;
		
		if (s == "extract") {
			std::cout << pop_max(&tab) << "\n";
			//max_heapify(&tab,tab.size()-1);
			/*
			for (auto i{ static_cast<int>(tab.size()) / 2  }; i > 0; --i)
				max_heapify(&tab, i - 1);
			*/
		}else {
			sll t;
			std::cin >> t;
			insert( &tab, std::move(t) );
		}
		
//		p();
	}

	return 0;
}



Measured memory_bytes: 11104