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

// Maximální velikost haldy. Mohli bychom dělat rostoucí, ale o tom ta úloha není.
#define MAX 1024

struct halda {
	int dolety[MAX + 1]; // Nulu nepoužijeme
	size_t velikost;
	int orientace; // 1 ‒ minimová, -1 ‒ maximová
};

// Bublání hald
void nahoru(struct halda *halda, size_t index) {
	while (index > 1) {
		size_t otec = index / 2;
		if (halda->dolety[otec] * halda->orientace > halda->dolety[index] * halda->orientace) {
			int tmp = halda->dolety[otec];
			halda->dolety[otec] = halda->dolety[index];
			halda->dolety[index] = tmp;
			index = otec;
		} else
			break; // Už neprohazujeme, vše OK
	}
}

void dolu(struct halda *halda, size_t index) {
	while (index * 2 <= halda->velikost) {
		size_t levy = index * 2;
		size_t pravy = index * 2 + 1;
		size_t mensi = levy;
		if (pravy <= halda->velikost && halda->dolety[pravy] * halda->orientace < halda->dolety[levy] * halda->orientace)
			mensi = pravy;
		if (halda->dolety[index] * halda->orientace > halda->dolety[mensi] * halda->orientace) {
			int tmp = halda->dolety[index];
			halda->dolety[index] = halda->dolety[mensi];
			halda->dolety[mensi] = tmp;
			index = mensi;
		} else
			break; // Už vše OK
	}
}

// Operace s haldami
void vloz(struct halda *halda, int dolet) {
	halda->dolety[++ halda->velikost] = dolet;
	nahoru(halda, halda->velikost);
}

int odeber(struct halda *halda) {
	assert(halda->velikost);
	int vysledek = halda->dolety[1];
	halda->dolety[1] = halda->dolety[halda->velikost --];
	dolu(halda, 1);
	return vysledek;
}

// Haldy
struct halda leva = {
	.orientace = -1
}, prava = {
	.orientace = 1
};
// Operace s raketami
struct halda *median(void) { // Urči, ve které haldě je medián
	if (leva.velikost > prava.velikost)
		return &leva;
	else
		return &prava;
}

void vyrovnej(void) {
	if (leva.velikost > prava.velikost + 1)
		vloz(&prava, odeber(&leva));
	else if (prava.velikost > leva.velikost + 1)
		vloz(&leva, odeber(&prava));
}

int vystrel(void) {
	int vysledek = odeber(median());
	vyrovnej();
	return vysledek;
}

void pridej(int dolet) {
	if (!leva.velikost && !prava.velikost)
		vloz(&leva, dolet);
	else {
		int med = median()->dolety[1];
		struct halda *cil = dolet < med ? &leva : &prava;
		vloz(cil, dolet);
		vyrovnej();
	}
}

// Obal na načítání
int main(int argc, const char *argv[]) {
	(void)argc;
	(void)argv;
	for (;;) { // Nikdy nekončíme
		char ukol;
		scanf(" %c", &ukol);
		if (ukol == 'v') {
			printf("%d\n", vystrel());
		} else if (ukol == 'p') {
			int dolet;
			scanf("%d", &dolet);
			pridej(dolet);
		} else {
			fprintf(stderr, "Úkol %c neznám\n", ukol);
		}
	}
}