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

class Node {
public:
	long key;
	int parent, left, right;
	Node() {
		key = -1;
		parent = left = right = -1;
	}
};

class CompleteBT {
public:
	int size;
	std::vector<long> heap;
	std::vector<Node> nodes;
	CompleteBT(int s, std::vector<long> inHeap) {
		heap = inHeap;
		size = s;
		Node n;
		nodes.assign(size, n);
	}
	CompleteBT() {
		size = 0;
	}
	void makeTree() {
		for (int i = 0; i < size; i++) {
			nodes[i].key = heap[i];
			if (i > 0) {
				nodes[i].parent = (i - 1) / 2;
			}
			if ((i + 1) * 2 - 1 < size) {
				nodes[i].left = (i + 1) * 2 -1;
			}
			if ((i + 1) * 2 < size) {
				nodes[i].right = (i + 1) * 2;
			}
		}
	}
	void topTree(int i) {
		int max = -1;
		int l = nodes[i].left;
		int r = nodes[i].right;
		if (l < size && nodes[l].key > nodes[i].key) {
			max = l;
		}
		else {
			max = i;
		}
		if (r < size && nodes[r].key > nodes[max].key) {
			max = r;
		}
		if (max != i) {
			long tmp = nodes[i].key;
			nodes[i].key = nodes[max].key;
			nodes[max].key = tmp;
			topTree(max);
		}
	}
	void bottomTree(int i) {
		int parent = i == 0 ? -1 : (i - 1) / 2;
		if (parent >= 0 && nodes[parent].key < nodes[i].key) {
			long tmp = nodes[parent].key;
			nodes[parent].key = nodes[i].key;
			nodes[i].key = tmp;
			bottomTree(parent);
		}
	}
	long pop() {
		long max = nodes[0].key;
		nodes[0].key = nodes[size - 1].key;
		nodes.pop_back();
		size -= 1;

		if (size > 0) {
			topTree(0);
		}
		return max;
	}
	void insert(long key) {
		Node n;
		n.key = key;
		n.parent = size == 0 ? -1 : (size - 1) / 2;
		n.left = (size + 1) * 2 - 1;
		n.right = (size + 1) * 2;
		nodes.push_back(n);
		size += 1;

		bottomTree(size - 1);
	}
};

void maxHeapify(const int i, std::vector<long> &heap) {
	int l = (i + 1) * 2 - 1; // 左の子
	int r = (i + 1) * 2; // 右の子
	int size = heap.size();

	int max = -1;
	if (l < size && heap[l] > heap[i]) {
		max = l;
	}
	else {
		max = i;
	}
	if (r < size && heap[r] > heap[max]) {
		max = r;
	}
	if (max != i) {
		long tmp = heap[i];
		heap[i] = heap[max];
		heap[max] = tmp;
		maxHeapify(max, heap);
	}
}

void buildMaxHeap(std::vector<long> &heap) {
	for (int i = (heap.size() - 1) / 2; i >= 0; i--) {
		maxHeapify(i, heap);
	}
}

void outputCBT(const CompleteBT &tree) {
	for (int i = 0; i < tree.size; i++) {
		std::cout << "node " << i + 1 << ": key = " << tree.nodes[i].key << ", ";
		if (tree.nodes[i].parent >= 0) {
			std::cout << "parent key = " << tree.nodes[tree.nodes[i].parent].key << ", ";
		}
		if (tree.nodes[i].left >= 0) {
			std::cout << "left key = " << tree.nodes[tree.nodes[i].left].key << ", ";
		}
		if (tree.nodes[i].right >= 0) {
			std::cout << "right key = " << tree.nodes[tree.nodes[i].right].key << ", ";
		}
		std::cout << std::endl;
	}
}

#if 0
int main() {
	int size;
	std::cin >> size;
	std::vector<long> heap(size);
	for (int i = 0; i < size; i++) {
		std::cin >> heap[i];
	}

	buildMaxHeap(heap);

	//CompleteBT tree(size, heap);
	//tree.makeTree();

	//outputCBT(size, tree);
	for (int i = 0; i < size; i++) {
		std::cout << " " << heap[i];
	}
	std::cout << std::endl;
}
#endif

int main() {
	std::string s;
	CompleteBT tree;
	while (1) {
		std::cin >> s;
		if (s == "end") {
			break;
		}
		if (s == "insert") {
			long key;
			std::cin >> key;
			tree.insert(key);
		}
		if (s == "extract") {
			long max = tree.pop();
			std::cout << max << std::endl;
		}
	}
}


Measured memory_bytes: 27364