#include <stdio.h>
#include <string.h>
#define MAX 2000000000
#define INF 2000000001

void swap(int, int);
int parent(int);
int left(int);
int right(int);
void risePriority(int);
void maxHeapify(int);
void insert(int);
int extract();

int A[MAX];
int length;

int main()
{
  int key;
  char order[8];
	
  length = 0;
  A[0] = INF;
	
  while(1)
    {
      scanf("%s", order);
		
      if(strcmp(order, "insert") == 0)
	{
	  scanf("%d", &key);
	  insert(key);
	}
      if(strcmp(order, "extract") == 0)
	{
	  printf("%d\n", extract());
	}
      if(strcmp(order, "end") == 0)
	{
	  break;
	}
    }
	
  return 0;
}

void swap(int i1, int i2)
{
  int tmp;

  tmp = A[i1];
  A[i1] = A[i2];
  A[i2] = tmp;
}

int parent(int i)
{
  return i / 2;
}

int left(int i)
{
  return 2 * i;
}

int right(int i)
{
  return 2 * i + 1;
}

void risePriority(int i)
{
  int p;
  p = parent(i);
  printf("%d:%d %d:%d\n", i, A[i], p, A[p]);
	
  if(A[i] > A[p])
    {
      swap(i, p);
      risePriority(p);
    }
}

void maxHeapify(int i)
{
  int l, r;
  int largest;

  l = left(i);
  r = right(i);

  largest = i;
  if(l <= length && A[l] > A[largest])
    largest = l;
  if(r <= length && A[r] > A[largest])
    largest = r;

  if(largest != i)
    {
      swap(i, largest);
      maxHeapify(largest);
    }
}

void insert(int k)
{
  length++;
  A[length] = k;
	
  risePriority(length);
}

int extract()
{
  int ret;
	
  ret = A[1];
  swap(1, length);
  length--;
  maxHeapify(1);
	
  return ret;
}