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

typedef struct node{
  long key;
  struct node *next;
}Node;

Node *insert(Node *root,long key){
  Node *p = (Node*)malloc(sizeof(Node));
  p->next = NULL;
  p->key = key;
  Node *x = root,*y = NULL;
  while(x != NULL) {
    if(x->key < key) break;
    y = x;
    x = x->next;
  }
  if(y == NULL) {
    p->next = x;
    return p;
  }
  y->next = p;
  p->next = x;
  return root;
}

Node *extract(Node *root) {
  printf("%ld\n",root->key);
  Node *x = root->next;
  free(root);
  return x;
}

int main()
{
  long key;
  char command[8];
  Node *root = NULL;
  while(1) {
    scanf("%s",command);
    if(strcmp(command,"insert") == 0) {
      scanf("%ld",&key);
      root = insert(root,key);
    }
    if(strcmp(command,"extract") == 0) {
      root = extract(root);
    }
    if(strcmp(command,"end") == 0) break;
  }
  return 0;
}