#include<fstream>
#include<vector>
#include<cstring>

using namespace std;

ifstream cin("heapuri.in");
ofstream cout("heapuri.out");

vector<int>v(1, 0);
vector<int>indice(1,0);
vector<int>ord(1,0);

bool empty()
{
    return v.size() == 1;
}

void up(int pos)
{
    if(pos >= v.size())
    {
        return;
    }
    while(pos > 1 && v[pos] < v[pos / 2])
    {
        swap(v[pos], v[pos / 2]);
        swap(ord[indice[pos]], ord[indice[pos/2]]);
        swap(indice[pos], indice[pos/2]);
        pos /= 2;
    }
}

void down(int pos)
{
    while(2 * pos < v.size())
    {
        int min_fiu = 2 * pos;
        if(2 * pos + 1 < v.size() && v[2 * pos + 1] < v[min_fiu])
        {
            min_fiu = 2 * pos + 1;
        }
        if(v[min_fiu] >= v[pos])
        {
            break;
        }
        swap(v[pos], v[min_fiu]);
        swap(ord[indice[pos]], ord[indice[min_fiu]]);
        swap(indice[pos], indice[min_fiu]);
        pos = min_fiu;
    }
}

int main()
{
    int t; cin >> t;
    int cnt = 0;
    for(int i = 0; i < t; i++)
    {
        char cerinta; cin >> cerinta;
       // cout << cerinta << " " << i << "\n";
        if(cerinta == '1')
        {
            int x; cin >> x;
            v.push_back(x);
            indice.push_back(++cnt);
            ord.push_back(v.size() - 1);
            up(v.size() - 1);
        }
        else if(cerinta == '2')
        {
            int poz; cin >> poz;
            int ind = ord[poz];
            swap(v[ind], v[v.size() - 1]);
            swap(ord[indice[ind]], ord[indice.back()]);
            swap(indice[ind], indice.back());
            v.pop_back();
            indice.pop_back();
            up(ind);
            down(ind);
        }
        else
        {
            cout << v[1] << "\n";
        }
    }
    return false;
}