#include <fstream>
#include <vector>
#include <algorithm>

/*
    first  -- value
    second -- order index
*/

typedef std::pair<unsigned int, unsigned int> heap_data;

inline void heap_up (std::vector<heap_data> &heap, std::vector<unsigned int> &order, unsigned int index)
{
    if (heap.size() > 1)
    {
        unsigned int value(heap[index].first);
        unsigned int father((index - 1) >> 1);
        while (value < heap[father].first)
        {
            std::swap(order[heap[father].second],order[heap[index].second]);
            heap[index].first = heap[father].first;
            std::swap(heap[index].second,heap[father].second);
            index = father;
            if (father)
            {
                --father;
                father >>= 1;
            }
            else
                break;
        }
        heap[index].first = value;
    }
}

inline void heap_down (std::vector<heap_data> &heap, std::vector<unsigned int> &order, unsigned int index)
{
    unsigned int size(heap.size());
    if (size > 1)
    {
        unsigned int left((index << 1) + 1), right(left + 1), smallest;
        while (true)
        {
            if (left < size && heap[left].first < heap[index].first)
                smallest = left;
            else
                smallest = index;
            if (right < size && heap[right].first < heap[smallest].first)
                smallest = right;
            if (smallest == index)
                break;
            std::swap(order[heap[index].second],order[heap[smallest].second]);
            std::swap(heap[index],heap[smallest]);
            index = smallest;
            left = (index << 1) + 1;
            right = left + 1;
        }
    }
}

int main (void)
{
    std::ifstream input("heapuri.in");
    unsigned int n;
    input >> n;
    char operation;
    unsigned int number;
    std::ofstream output("heapuri.out");
    std::vector<heap_data> heap;
    std::vector<unsigned int> order;
    do
    {
        input >> operation;
        if (operation == '3')
            output << heap.front().first << '\n';
        else
        {
            input >> number;
            if (operation == '2')
            {
                --number;
                number = order[number];
                order[heap.back().second] = order[heap[number].second];
                heap[number] = heap.back();
                heap.pop_back();
                if (number > 0 && heap[number].first < heap[((number - 1) >> 1)].first)
                    heap_up(heap,order,number);
                else
                    heap_down(heap,order,number);
            }
            else
            {
                unsigned int size(heap.size());
                heap.push_back(std::make_pair(number,order.size()));
                order.push_back(size);
                heap_up(heap,order,size);
            }
        }
        --n;
    }
    while (n);
    input.close();
    output.close();
    return 0;
}