#include <stdio.h>
#include <stdlib.h>

#define ORIGIN 1
#define SWAP(a, b, v) v = a, a = b, b = v
#define parent(i) ((i) / 2)
#define left(i) (2 * (i))
#define right(i) (2 * (i) + 1)

int a[2000001]; /* 8MB */

/* ヒントがないのでwikipedia参照 */

void
up_heap(int *a, int n, int i)
{
	int p = parent(i);
	int g;

	g = (ORIGIN <= p && a[p] < a[i]) ? p : i;

	if (g != i) {
		SWAP(a[i], a[g], p);
		up_heap(a, n, g);
	}
}

void
down_heap(int *a, int n, int i)
{
	int l = left(i);
	int r = right(i);
	int g;

	g = (l <= n && a[l] > a[i]) ? l : i;
	g = (r <= n && a[r] > a[g]) ? r : g;

	if (g != i) {
		SWAP(a[i], a[g], l);
		down_heap(a, n, g);
	}
}

int
main(void)
{
	int i, p, n = 0;
	int v;
	char cmd[16];

	while (scanf("%s", cmd) != EOF) {
		switch (cmd[2]) {
		case 's': /* in[s]ert */
			scanf("%d", &v);
			a[++n] = v;
			up_heap(a, n, n);
			break;
		case 't': /* ex[t]ract */
			printf("%d\n", a[ORIGIN]);
			a[ORIGIN] = a[n--];
			down_heap(a, n, ORIGIN);
			break;
		default: /* end */
			return 0;
		}
	}


	return 0;
}

