# include <cstdio>

# define FIN "heapuri.in"
# define FOUT "heapuri.out"
# define MAXN 200005

int N, Nh, op, i, ct, aux, x;
int X[MAXN];
int Pos[MAXN];
int Heap[MAXN];

    void up(int i, int N)
    {
        int tata, fiu;
        
        fiu = i; tata = i >> 1;
        
        while (tata && X[Heap[tata]] > X[Heap[fiu]])
           {
              Pos[Heap[tata]] = fiu;
              Pos[Heap[fiu]] = tata;
              aux = Heap[tata];
              Heap[tata] = Heap[fiu];
              Heap[fiu] = aux;
              fiu = tata;
              tata >>= 1;
           }
    }
    
    void down(int i, int N)
    {
        int tata, fiu;
        
        tata = i; fiu = i << 1;
        
        while (fiu <= N)
           {
              if (fiu < N && X[Heap[fiu]] > X[Heap[fiu+1]])
                fiu++;
              if (X[Heap[tata]] > X[Heap[fiu]])
                {
                   Pos[Heap[fiu]] = tata;
                   Pos[Heap[tata]] = fiu;
                   aux = Heap[tata];
                   Heap[tata] = Heap[fiu];
                   Heap[fiu] = aux;
                   tata = fiu;
                   fiu <<= 1;
                } else
              fiu = N + 1;
           }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d",&N);
        
        Nh = ct = 0;
        for (i = 1; i <= N; ++i)
           {
              scanf("%d",&op);
              if (op == 1)
                {
                   scanf("%d",&X[++ct]);
                   Heap[++Nh] = ct;
                   Pos[ct] = Nh;
                   up(Nh, Nh);
                } else
              if (op == 2)
                {
                   scanf("%d",&x);                
                   
                   Pos[Heap[Nh]] = Pos[x];
                   Heap[Pos[x]] = Heap[Nh];
                   Nh--;
                   
                   if (Pos[x] && X[Heap[Pos[x]/2]] > X[Heap[Pos[x]]])
                     up(Pos[x], Nh);
                   else
                     down(Pos[x], Nh);
                } else
              if (op == 3) printf("%d\n",X[Heap[1]]);
           }
        
        return 0;
    }