#include<fstream>
#include<algorithm>
#define Nmax 300002
#define Big 1000000010
using namespace std;

ifstream f("heapuri.in");
ofstream g("heapuri.out");

long int n,a[Nmax],P[Nmax],C[Nmax],nr,N;

void heaps();
void combine(int i,int n);
void push(int n);

int main()
{
  heaps();
  f.close();
  g.close();
  return 0;
}

void heaps()
{
  int x,pos,c,i;
  f>>n;
  for (i=1;i<=n;++i)
  {
    f>>c;
    if (c==3)
    {
      g<<a[1]<<'\n';
      continue;
    }
    else if (c==1)
    {
      f>>x;
      ++N;
      ++nr;
      a[N]=x;
      P[N]=nr;
      C[nr]=N;
      push(N);
    }
    else if (c==2)
    {
      f>>x;
      pos=C[x];
      swap(a[pos],a[N]);
      //swap(C[P[pos]],C[P[N]]);
      swap(P[pos],P[N]);
      C[P[pos]]=pos;
      C[P[N]]=N;
      
      //a[pos]=Big;
      --N;
      combine(pos,N);
      //--N;
    } 
  }    
}

void combine(int i,int n)
{
  int c,t,aux,paux;
  aux=a[i];
  paux=P[i];
  t=i;
  c=t*2;
  while (c<=n)
  {
    if (c+1<=n&&a[c+1]<a[c])
      ++c;
    if (a[c]<aux)
    {
      a[t]=a[c];
      C[P[c]]=t;
      P[t]=P[c];
      t=c;
      c*=2;
    }
    else c=n+1;
  }
  a[t]=aux;
  C[paux]=t;
  P[t]=paux;
}
  

void push(int n)
{
  int aux,paux,c,t;
  aux=a[n];
  paux=P[n];
  t=n/2;
  c=n;
  while (t&&a[t]>aux)
  {
      a[c]=a[t];
      C[P[t]]=c;
      P[c]=P[t];
      c=t;
      t/=2;
  }
  a[c]=aux;
  C[paux]=c;
  P[c]=paux;
}