#include <cassert>
#include <functional>
#include <utility>
#include <vector>

template <typename T, class Container = std::vector<T>,
	class Compare = std::less<typename Container::value_type>>
	class IntervalHeap {

	public:
		using container_type = Container;
		using value_compare = Compare;
		using value_type = typename container_type::value_type;
		using reference = typename container_type::reference;
		using const_reference = typename container_type::const_reference;
		using size_type = typename container_type::size_type;

	protected:
		container_type c;
		value_compare comp;

	private:
		static constexpr size_type z = ~static_cast<size_type>(1);
		bool normalize(const size_type x, const size_type y) {
			if (!comp(c[y], c[x]))
				return false;
			std::swap(c[x], c[y]);
			return true;
		}
		void build() {
			const size_type s = size() + 1;
			if (s & 1) {
				normalize(s & z, s);
				buildmin(s >> 1);
				buildmax(s >> 1);
				return;
			}
			if (s == 2)
				return;
			if (normalize(s, s >> 1 | 1))
				buildmax(s >> 2);
			buildmin(s >> 1);
		}
		void buildmin(size_type i) {
			while (i > 1 && normalize(i & z, i << 1))
				i >>= 1;
		}
		void buildmax(size_type i) {
			while (i > 1 && normalize(i << 1 | 1, i | 1))
				i >>= 1;
		}

	public:
		explicit IntervalHeap(const value_compare &x = Compare()) : c(2), comp(x) {}
		bool empty() const { return c.size() == 2; }
		size_type size() const { return c.size() - 2; }
		const_reference min() const {
			assert(!empty());
			return c[2];
		}
		const_reference max() const {
			assert(!empty());
			return size() == 1 ? c[2] : c[3];
		}
		void push(const value_type &x) {
			c.push_back(x);
			build();
		}
		void push(value_type &&x) {
			c.push_back(std::move(x));
			build();
		}
		template <class... Args> void emplace(Args &&... args) {
			c.emplace_back(std::forward<Args>(args)...);
			build();
		}
		void pop_min() {
			assert(!empty());
			const size_type s = size() + 1;
			std::swap(c[2], c[s]);
			c.pop_back();
			size_type i = 4;
			while (i + 3 < s) {
				if (!comp(c[i], c[i | 2]))
					i |= 2;
				if (!normalize(i >> 1 & z, i))
					return;
				normalize(i, i | 1);
				i <<= 1;
			}
			if (s <= i)
				return;
			if ((i | 2) < s && comp(c[i | 2], c[i]))
				i |= 2;
			normalize(i >> 1 & z, i);
			if ((i | 1) < s)
				normalize(i, i | 1);
		}
		void pop_max() {
			assert(!empty());
			const size_type s = size() + 1;
			if (s == 2)
				return pop_min();
			std::swap(c[3], c[s]);
			c.pop_back();
			size_type i = 5;
			while (i < s) {
				if ((i | 2) < s && !comp(c[i | 2], c[i]))
					i |= 2;
				if (!normalize(i, i >> 1 | 1))
					break;
				normalize(i & z, i);
				i = (i & z) << 1 | 1;
			}
		}
};


#include<cstdio>
#include<string>
#include<vector>
void scan(std::string &s) {
	s.clear();
	int c = fgetc(stdin);
	while (c == ' '||c == '\n') c = fgetc(stdin);
	while (c != ' '&&c != '\n') {
		s.push_back(c);
		c = fgetc(stdin);
	}
}

int main() {
	IntervalHeap<int,std::vector<int>,std::greater<int>> Q;
	std::string s;
	int k;
	scan(s);
	while (s[2] != 'd') {
		if (s[0] == 'i') {
			scanf("%d", &k);
			Q.emplace(k);
		}
		else {
			printf("%d\n", Q.min());
			Q.pop_min();
		}
		scan(s);
	}
	return 0;
}


Measured memory_bytes: 6680