#include <bits/stdc++.h>
using namespace std;

template<class Key, class Compare = less<Key>>
struct FibHeap {
	struct node; using np = node*;
	using u32 = uint_fast32_t;
	struct node {
		Key key;
		np left, right;
		np par, child;
		u32 degree;
		bool mark;
		node(Key k) : key(k), left(this), right(this), par(nullptr), child(nullptr), degree(0), mark(false) {}
		node() : key(), left(this), right(this), par(nullptr), child(nullptr), degree(0), mark(false) {}
	};
	np maximum;
	np roots;
	u32 n;
	FibHeap() : maximum(nullptr), n(0) {
		roots = new node();
	}
	np push(Key k) {
		n++;
		np x = new node(move(k));
		insert_node_to_roots(x);
		// if (!maximum) return maximum = x;
		if (!maximum) maximum = x;
		update_maximum(x);
		return x;
	}
	void pop() {
		np z = maximum;
		if (z) {
			for (np x : make_list_vector(z->child)) {
				insert_node_to_roots(x);
			}
			cut_par(z); cut_list_sub(z);
			if (roots == roots->right) maximum = nullptr;
			else {
				Consolidate();
			}
			n--;
		}
	}
	const Key& top() const {
		return maximum->key;
	}
	void check() const {
		bool f = roots == roots->right;
		for (np x : make_roots_vector()) {
			assert(!x->par);
			f = f || x == maximum;
		}
		assert(f);
		check_dfs(roots);
	}
	u32 size() const {return n;}
private:
	int check_dfs(np n) const {
		if (!n) return 0;
		vector<np> ls = make_list_vector(n);
		int d = ls.size();
		for (auto x : ls) {
			assert(x->left->right == x);
			assert(x->degree == u32(check_dfs(x->child)));
			if (x->child) assert(x->child->par == x);
		}
		return d;
	}
	inline void cut_par(np x) {
		if (!x->par) return;
		x->par->degree--;
		if (x->par->child == x) {
			if (x->right == x) x->par->child = nullptr;
			else x->par->child = x->right;
		}
	}
	inline void insert_node_to_roots(np x) {
		// assert(x);
		x->par = nullptr;
		x->left = roots;
		x->right = roots->right;
		roots->right = roots->right->left = x;
	}
	inline void insert_node_to_list(np& list, np n) {
		if (!list) list = n->left = n->right = n;
		else {
			n->left = list;
			n->right = list->right;
			list->right = list->right->left = n;
		}
	}
	inline void update_maximum(np x) {
		// assert(x && maximum);
		if (Compare()(maximum->key, x->key)) maximum = x;
	}
	inline void cut_list(np x) {
		cut_list_sub(x);
		x->left = x->right = x;
	}
	inline void cut_list_sub(np x) {
		x->left->right = x->right;
		x->right->left = x->left;
	}
	inline vector<np> make_list_vector(np n) const {
		if (!n) return move(vector<np>(0));
		vector<np> res(1, n);
		for (np nn = n->right; nn != n; nn = nn->right) {
			res.push_back(nn);
		}
		return move(res);
	}
	inline vector<np> make_roots_vector() const {
		vector<np> res;
		for (np n = roots->right; n != roots; n = n->right) {
			res.push_back(n);
		}
		return move(res);
	}
	inline void Consolidate() {
		constexpr double phi = (1 + sqrt(5)) / 2;
		int sz = 2;
		for (double p = phi; p < n; p *= phi, sz++);
		vector<np> A(sz, nullptr);
		// assert(!maximum->par);
		for (np x : make_roots_vector()) {
			u32 d = x->degree;
			while (np y = A[d]) {
				if (Compare()(x->key, y->key)) swap(x, y);
				Link(y, x);
				A[d] = nullptr;
				d++;
			}
			A[d] = x;
		}
		maximum = roots->right;
		for (np x = roots->right->right; x != roots; x = x->right) update_maximum(x);
	}
	inline void Link(np child, np par) {
		// assert(child != par);
		// assert(!child->par);
		// assert(!par->par);
		cut_list_sub(child);
		insert_node_to_list(par->child, child);
		child->par = par;
		par->degree++;
		child->mark = false;
	}
};


int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	FibHeap<int> q;
	string s;
	while (cin >> s, s != "end") {
		if (s[0] == 'i') {
			int x; cin >> x;
			q.push(x);
		} else {
			cout << q.top() << endl;
			q.pop();
		}
	}
	q.check();
}



Measured memory_bytes: 96868