#include <stdio.h>

#define SIZE 2000000

int _IO_default_xsputn (FILE *f, const void *data, size_t n)
{
  const char *s = (char *) data;
  size_t more = n;
  if (more <= 0)
    return 0;
  for (;;)
    {
      /* Space available. */
      if (f->_IO_write_ptr < f->_IO_write_end)
        {
          size_t count = f->_IO_write_end - f->_IO_write_ptr;
          if (count > more)
            count = more;
          if (count > 20)
            {
              f->_IO_write_ptr = __mempcpy (f->_IO_write_ptr, s, count);
              s += count;
            }
          else if (count)
            {
              char *p = f->_IO_write_ptr;
              ssize_t i;
              for (i = count; --i >= 0; )
                *p++ = *s++;
              f->_IO_write_ptr = p;
            }
          more -= count;
        }
      if (more == 0 || _IO_OVERFLOW (f, (unsigned char) *s++) == EOF)
        break;
      more--;
    }
  return n - more;
}



int main() {
  int A[SIZE];
  int H=0;
  int i, l, largest, tmp, n;
  char com[21], buf[20];
  buf[19]='\n';
  char *p;
  do {
    fgets(com, 20, stdin);
    if (*com == 'i') {
      A[++H] = 0;
      p = com+7;
      while (*p!='\n') {
        A[H] = A[H]*10+*p-'0';
        p++;
      }

      for (i=H; i>1 && A[i>>1]<A[i];i>>=1) {
        tmp = A[i>>1];
        A[i>>1] = A[i];
        A[i] = tmp;
      }

    } else if (com[1]=='x') { // extract
      n = A[1];
      for (i=18; n>0; n/=10) buf[i--]=(n%10)+'0';
      fputs_unlocked(buf+i+1, stdout);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i<<1;
        if (l < H && A[l] > A[i])        largest = l;
        else         largest = i;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (com[2]!='d');
  return 0;
}

