#include<stdio.h>

#define INPUT "heapuri.in"
#define OUTPUT "heapuri.out"
#define NMAX 200001

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long A[ NMAX ], Heap[ NMAX ], PHeap[ NMAX ];
long cont, Poz;

inline void twist(long &_X, long &_Y)
{
  _X = _X + _Y;
  _Y = _X - _Y;
  _X = _X - _Y;
}

void AddHeap(long _X)
{
  if(_X/2 < 1 || A[ Heap[ _X/2 ] ] < A[ Heap[ _X ] ])
    return;

  twist(Heap[ _X/2 ], Heap[ _X ]);
  PHeap[ Heap[ _X/2 ] ] = _X/2;
  PHeap[ Heap[ _X ] ] = _X;

  AddHeap(_X/2);
}

void ExtractHeap(long _X)
{
  if( 2 * _X > Poz) return;
  if( 2 * _X + 1 > Poz && A[ Heap[ 2 * _X ] ] > A[ Heap[ _X ] ]) return;
  if( 2 * _X + 1 <= Poz && A[ Heap[ 2 * _X ] ] > A[ Heap[ _X ] ] && A[ Heap[ 2 * _X + 1 ] ] > A[ Heap[ _X ] ]) return;

  if( 2 * _X + 1 > Poz)
  {
    if(A[ Heap[ 2 * _X ] ] < A[ Heap[ _X ] ])
    {
      twist(Heap[ 2 * _X ], Heap[ _X ]);
      PHeap[ Heap[ 2 * _X ] ] = 2 * _X;
      PHeap[ Heap[ _X ] ] = _X;

      ExtractHeap(2 * _X);
    }
  }
  else
  {
    if(A[ Heap[ 2 * _X] ] < A[ Heap[ 2 * _X + 1 ] ] && A[ Heap[ 2 * _X ] ] < A[ Heap[ _X ] ])
    {
      twist(Heap[ 2 * _X ], Heap[ _X ]);
      PHeap[ Heap[ 2 * _X ] ] = 2 * _X;
      PHeap[ Heap[ _X ] ] = _X;
      ExtractHeap( 2 * _X );
    }
    else
    if(A[ Heap[ 2 * _X] ] > A[ Heap[ 2 * _X + 1 ] ] && A[ Heap[ 2 * _X + 1] ] < A[ Heap[ _X ] ])
    {
      twist(Heap[ 2 * _X + 1], Heap[ _X ]);
      PHeap[ Heap[ 2 * _X + 1] ] = 2 * _X + 1;
      PHeap[ Heap[ _X ] ] = _X;
      ExtractHeap( 2 * _X + 1);
    }
    else return;
  }
}

int main()
{
  long N, X;
  int Code;

  cont = 0;
  Poz = 0;

  fscanf(fin, "%ld", &N);

  for(long i = 0; i < N; ++i)
  {
    fscanf(fin, "%d", &Code);

    if(Code == 1)
    {
      fscanf(fin, "%ld", &A[ ++cont ]);
      Heap[ ++Poz ] = cont;
      PHeap[ cont ] = Poz;

      AddHeap(Poz);
    }
    else
    if(Code == 2)
    {
      fscanf(fin, "%ld", &X);
      A[ X ] = -1;

      AddHeap( PHeap[ X ] );

      PHeap[ Heap[ 1 ] ] = 0;
      Heap[ 1 ] = Heap[ Poz-- ];
      PHeap[ Heap[ 1 ] ] = 1;

      ExtractHeap(1);
    }
    else
      fprintf(fout, "%ld\n", A[ Heap[ 1 ] ]);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}