/* ALDS1_9_C: PriorityQueue */
/* 20181129 AOJ */

#define _CRT_SECURE_NO_WARNINGS
#define N 2000001
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void insert(int *priorityQueue, int key);
int extract(int *priorityQueue);
void maxHeapify(int *priorityQueue, int i);
void swap(int *x, int * y);

int id;

int main( )
{
	int  i, key;
	char cmd[8];
	int *priorityQueue = (int *)malloc(sizeof(int) * N);

	id = 0;
	while(1)
	{
		scanf("%s", cmd);
		if(strcmp(cmd, "insert") == 0)
		{
			scanf("%d", &key);
			insert(priorityQueue, key);
		}
		else if (strcmp(cmd, "extract") == 0)
		{
			printf("%d\n", extract(priorityQueue));
		}else
		{
			break;
		}
	}

	return 0;
}

void insert(int *priorityQueue, int key)
{
	int i, parent;

	priorityQueue[++id] = key;
	
	i = id;
	while(i > 1)
	{
		parent = i / 2;
		if (priorityQueue[i] > priorityQueue[parent])
		{
			swap(priorityQueue + i, priorityQueue + parent);
			i = parent;
		} 
		else
		{
			break;
		}	
	}
}

int extract(int *priorityQueue) {
	int ret, i;

	ret =  priorityQueue[1];
	priorityQueue[1] = priorityQueue[id--];
	maxHeapify(priorityQueue, 1);

	return ret;
}

void maxHeapify(int *heap, int i) {
	int left, right, maxId;
	
	left = 2 * i;
	right = left + 1;
	if(left <= id && heap[left] > heap[i])
	{
		maxId = left;
	}
	else
	{
		maxId = i;
	}

	if(right <= id && heap[right] > heap[maxId])
	{
		maxId = right;
	}

	if(maxId != i)
	{
		swap(heap + i, heap + maxId);
		maxHeapify(heap, maxId);
	}
}

void swap(int *x, int * y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}
