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

using namespace std;

const char iname[] = "heapuri.in";
const char oname[] = "heapuri.out";

vector <int> list;

class Treap {
    class Node {
    public:
        int key, pr, cntr;
        Node *l, *r;
        Node(const int key) {
            this->key = key, l = r = NULL, pr = rand() + 1, cntr = 1;
        }
    };
    void insert(Node *&, const int) ;
    void erase(Node *&, const int) ;
    void rotleft(Node *&) ;
    void rotright(Node *&) ;
    void balance(Node *&) ;
public:
    Node *root;
    Treap() : root(NULL) {
        srand(unsigned(time(NULL)));
    }
    void insert(const int key) {
        insert(root, key);
    }
    void erase(const int key) {
        erase(root, key);
    }
    int ask(void) {
        Node *p;
        for (p = root; p->l != NULL; p = p->l) ;
        return p->key;
    }
};

void Treap::insert(Node *&r, const int key) {
    if (r == NULL) {
        r = new Node(key);   return ;
    }
    if (key == r->key) {
        r->cntr ++;  return ;
    }
    if (key < r->key)
        insert(r->l, key);
    else
        insert(r->r, key);
    balance(r);
}

void Treap::erase(Node *&r, const int key) {
    if (key < r->key)
        erase(r->l, key);
    else if (key > r->key)
        erase(r->r, key);
    else {
        if (r->cntr > 0) if ((-- r->cntr) > 0)  return ;
        if (r->l && r->r)
            (r->l->pr > r->r->pr) ? rotleft(r) : rotright(r);
        else if (r->l || r->r)
            r->l ? rotleft(r) : rotright(r);
        else
            delete r, r = NULL;

        if (r != NULL)   erase(r, key);
    }
}

void Treap::rotleft(Node *&r) {
    Node *tr = r->l; r->l = tr->r, tr->r = r, r = tr;
}

void Treap::rotright(Node *&r) {
    Node *tr = r->r; r->r = tr->l, tr->l = r, r = tr;
}

void Treap::balance(Node *&r) {
    if (r->l && r->l->pr > r->pr)
        rotleft(r);
    else if (r->r && r->r->pr > r->pr)
        rotright(r);
}

int main(void)
{
    Treap T;
    ifstream in(iname);  ofstream out(oname);
    int runs, n, m;
    for (in >> runs; runs --; ) {
        in >> n;
        if (n == 1)
            in >> m, T.insert(m), list.push_back(m);
        else if (n == 2)
            in >> m, T.erase(list[m - 1]);
        else
            out << T.ask() << "\n";
    }
    in.close(), out.close();
    return 0;
}