#define _CRT_SECURE_NO_WARNINGS
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <memory>
#include <utility>

template <class TotallyOrderedSet> class pairing_heap {

public:
	using set_type = TotallyOrderedSet;
	using value_type = typename set_type::value_type;
	using const_reference = const value_type &;
	using size_type = std::size_t;

private:
	struct node_t {
		value_type value;
		std::unique_ptr<node_t> left, right;
		template <class... Args>
		node_t(Args &&... args)
			: value(std::forward<Args>(args)...), left(), right() {}
	};
	using pointer = std::unique_ptr<node_t>;
	pointer root;
	size_type s;
	static pointer merge(pointer &&x, pointer &&y) {
		if (!x)
			return std::move(y);
		if (!(x->value>= y->value))
			std::swap(x, y);
		y->right = std::move(x->left);
		x->left = std::move(y);
		return std::move(x);
	}
	static pointer mergelist(pointer curr) {
		pointer head, temp;
		while (curr) {
			temp = std::move(curr->right);
			if (!temp) {
				curr->right = std::move(head);
				head = std::move(curr);
				break;
			}
			if (curr->value>= temp->value) {
				curr->right = std::move(head);
				head = std::move(curr);
				curr = std::move(temp->right);
				temp->right = std::move(head->left);
				head->left = std::move(temp);
			}
			else {
				curr->right = std::move(temp->left);
				temp->left = std::move(curr);
				curr = std::move(temp->right);
				temp->right = std::move(head);
				head = std::move(temp);
			}
		}
		if (head) {
			while (temp = std::move(head->right), temp) {
				if ((head->value>= temp->value)) {
					head->right = std::move(temp->right);
					temp->right = std::move(head->left);
					head->left = std::move(temp);
				}
				else {
					head->right = std::move(temp->left);
					temp->left = std::move(head);
					head = std::move(temp);
				}
			}
		}
		return std::move(head);
	}

public:
	pairing_heap() : root(), s(0) {}

	bool empty() const { return !root; }
	size_type size() const { return s; }

	const_reference top() const {
		assert(root);
		return root->value;
	}

	void push(const value_type &x) {
		root = merge(std::move(root), std::make_unique<node_t>(x));
		++s;
	}
	void push(value_type &&x) {
		root = merge(std::move(root), std::make_unique<node_t>(std::move(x)));
		++s;
	}
	template <class... Args> void emplace(Args &&... args) {
		root = merge(std::move(root),
			std::make_unique<node_t>(std::forward<Args>(args)...));
		++s;
	}

	void pop() {
		assert(root);
		root = mergelist(std::move(root->left));
		--s;
	}

	pairing_heap &meld(pairing_heap &other) {
		if (!other.empty()) {
			s += other.s;
			other.s = 0;
			root = merge(std::move(root), std::move(other.root));
		}
		return *this;
	}
	pairing_heap &operator+=(pairing_heap &other) { return meld(other); }
};
#include<cstdio>
#include<string>
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);
	}
}
template <class T> class ordered_set {
public:
	using value_type = T;

	static bool less_equal(const value_type &x, const value_type &y) {
		return x <= y;
	}
};

int main() {
	pairing_heap<ordered_set<int>> Q;
	std::string s;
	int k;
	while (scan(s),s[2] != 'd') {
		if (s[0] == 'i') {
			scanf("%d", &k);
			Q.push(k);
		}
		else {
			printf("%d\n", Q.top());
			Q.pop();
		}
	}
	return 0;
}


Measured memory_bytes: 33952