#include <iostream>
#include <stdio.h>      /* printf, scanf, puts */
#include <stdlib.h>     /* malloc, calloc, realloc, free, exit */
using namespace std;
 
class info {
    public:
        #define N_NAX 200003
        long long int index;
        static long long int value[N_NAX], position[N_NAX], swap_pos; 
        
        info() {
            index = -1;
            info::swap_pos = -1;
        }
 
        info& operator= (info& atrib) {
            if (this->index != -1) {
                if (info::position[this->index] != info::position[atrib.index]) {
                    info::swap_pos = info::position[this->index];
                    info::position[this->index]  = info::position[atrib.index];
                } else { 
                    info::position[this->index] = info::swap_pos;
                }
            }  
            this->index = atrib.index; 
            return *this;
        }
        friend bool operator<(const info& a, const info& b) {
            return value[a.index] > value[b.index];
        }
        friend bool operator>(const info& a, const info& b) {
            return value[a.index] < value[b.index];
        }
        friend bool operator<=(const info& a, const info& b) {
            return value[a.index] >= value[b.index];
        }
        friend bool operator>=(const info& a, const info& b) {
            return value[a.index] <= value[b.index];
        }
}aux;
long long int info::value[N_NAX];
long long int info::position[N_NAX];
long long int info::swap_pos;
 
template <class T>
class priority_queue {
public:
	#define MAX_HEAP_SIZE 200003 // 16 * 1024 16384
    long long int count_max_heap_size, heap_size;
    T* heap; // max heap
 
    #define father(node) (node >> 1)        // (node / 2)
    #define left_son(node) (node << 1)      // (node * 2)
    #define right_son(node) (node << 1 | 1) // (node * 2 + 1)
 
public:
	priority_queue() { // constructor
        count_max_heap_size = 1;
        heap_size = 0;
        heap = (T*) malloc(MAX_HEAP_SIZE * sizeof(T));
	}
 
private:
	void reallocating_heap_memory() {
		count_max_heap_size++;
 
		T* new_heap = (T*) realloc (heap, count_max_heap_size * MAX_HEAP_SIZE * sizeof(T));
 
		if (new_heap != NULL) {
			heap = new_heap;
		} else {
			free(heap);
			puts("Error (re)allocating memory for heap");
            exit(1);
		}
	}
 
	void swap(T &a, T &b) {
		T tmp;
        //plm();
		tmp = a;
        //plm();
		a = b;
        //plm();
		b = tmp;
        //plm();
	}
 
	int up(int node) { // percolate
      	while (1 < node && heap[father(node)] < heap[node]) {
            swap(heap[father(node)], heap[node]);
            node = father(node);
      	}
        return node;
	}
	
	int down(int node) { // sift
	    int son;
	    
	    do {
            son = 0; // assume that the node can't go lower
 
            // get the son with maximum value in heap
	        if (left_son(node) <= heap_size) {
                son = left_son(node);
                
                if (right_son(node) <= heap_size && heap[left_son(node)] < heap[right_son(node)]) {
                    son = right_son(node);
                }
                
                if (heap[son] < heap[node] ) {  // check if the node can go lower
                	son = 0;
                }
	        }
 
	        if (son) {
	        	swap(heap[son], heap[node]);
	        	node = son;
	        }
	    } while (son);
        return node;
	}
 
public:
	int size() { 
		return heap_size;
	}
 
	bool empty() {
		if (heap_size) {
			return false;
		}
		return true;
	}
 
	inline T top() { // peek
        if (heap_size)  {
           return heap[1];
        }
 
        try {
           throw 2;
        } catch (int e) {
           printf("An exception occurred. Exception Nr. %d. Call top without having elements in heap\n", e);
        }
 
        return heap[0]; // get rid of the warning
	}
 
	int push(T value) {
		heap_size++;
		if (heap_size >= count_max_heap_size * MAX_HEAP_SIZE - 1) {
			reallocating_heap_memory();
		}
 
		heap[heap_size] = value;
		return up(heap_size);
	}
 
    int del(int nod) {
        swap(heap[nod], heap[heap_size]);
        heap_size--;
        return down(nod);
    }
};
priority_queue<info>heap;
 
int n,k;
 
int main() {
 
    freopen ("heapuri.in","r",stdin);
    freopen ("heapuri.out","w",stdout);
 
    int i, type, x;
 
    scanf("%d", &n);
    for (i = k = 0; i < n; ++i) {
 
        scanf("%d", &type);
        if (type == 3) {
            printf("%lld\n", info::value[heap.top().index]);
        } else {
            scanf("%d", &x);
            if (type == 1) {
                ++k;
                aux.index = k;
                info::value[k] = x;
                info::position[k] = heap.size()+1;
                //info::position[k] = 
                heap.push(aux);
            } else {
                int ind = heap.heap[heap.size()].index;
                info::position[ind] = heap.del(info::position[x]);
            }
        }
    }
	return 0;
}