#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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

#define MAX_BUFF  1 << 22

vector <int> list;

char buffer[MAX_BUFF];

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);
}

void getn(char* &p, int& n) {
    for (; *p < '0' || *p > '9'; ++ p) ;
    for (n = 0; *p >= '0' && *p <= '9'; ++ p)
        n = n * 10 + (*p - '0');
}

int main(void)
{
    Treap T;
    FILE *fi = fopen(iname, "r");
    FILE *fo = fopen(oname, "w");

    buffer[fread(buffer, sizeof(char), MAX_BUFF, fi)] = 0;
    char *p = buffer;

    int runs, n, m;
    for (getn(p, runs); runs --; ) {
        getn(p, n);
        if (n == 1)
            getn(p, m), T.insert(m), list.push_back(m);
        else if (n == 2)
            getn(p, m), T.erase(list[m - 1]);
        else
            fprintf(fo, "%d\n", T.ask());
    }
    fclose(fi), fclose(fo);
    return 0;
}