// Copyright 2019 Nedelcu Horia ([email protected])

#ifndef __SKIPLIST_H__
#define __SKIPLIST_H__

#include <iostream>
#include <exception>
#include <stdlib.h>
#include <time.h>

#define N_MAX 200003
#define H_MAX 20
#define JUMP_TO_NULL -1

template<class T> class _node;
template<class T> class forward_multiskiplist;

template <class T>
class _node {
public:
    T data;
    int count;
    _node **forward;
    int *jump;

    _node(T, int, int count = 1);
    ~_node();
};

template <class T>
class forward_multiskiplist {
//private:
public:
    int capacity;
    int max_height;
    int num_elem;
    int *index_path;
    _node<T> *head, **path;

    int get_new_height();

public:
    forward_multiskiplist();
    ~forward_multiskiplist();
    int count_key(const T&);
    bool search(const T&);
    void insert(const T&, int count = 1);
    void erase(const T&, int count = 1);
    const T& operator[](int);
};

template <class T>
_node<T> :: _node(T data, int height, int count): data(data), count(count), forward(nullptr), jump(nullptr) {
    try {
        forward = new _node<T>*[height]();
        jump = new int[height]();

        for (int i = 0; i < height; ++i) {
            jump[i] = JUMP_TO_NULL;
        }
    } catch (std::exception& e) {
        std::cerr << "Standard exception: " << e.what() << '\n';
    }
}

template <class T>
_node<T> :: ~_node() {
    delete[] forward;
    delete[] jump;
}

template <class T>
int
forward_multiskiplist<T> :: get_new_height() {
    int height, random;

    for (height = 1, random = rand(); random & 1; random >>= 1, ++height) {
    }

    if (height > max_height) {
        height = max_height;
    }

    return height;
}

template <class T>
forward_multiskiplist<T> :: forward_multiskiplist(): capacity(N_MAX), max_height(H_MAX), num_elem(0), head(nullptr)  {
    T tmp = T();
    try {
        head = new _node<T>(tmp, max_height);
        path = new _node<T>*[max_height];
        index_path = new int[max_height]();
    } catch (std::exception& e) {
        std::cerr << "Standard exception: " << e.what() << '\n';
    }

    srand (time(NULL));
}

template <class T>
forward_multiskiplist<T> :: ~forward_multiskiplist() {
    _node<T>* tmp;

    while (head) {
        tmp = head;
        head = head->forward[0];
        delete tmp;
    }

    delete[] path;
    delete[] index_path;
}

template <class T>
int
forward_multiskiplist<T> :: count_key(const T& key) {
    _node<T> *it = head;

    for (int i = max_height - 1; i > -1; --i) {
        while (it->forward[i] && key > it->forward[i]->data) {
            it = it->forward[i];
        }
    }

    if (!it->forward[0] || key != it->forward[0]->data) {
        return 0;
    } else {
        return it->forward[0]->count;
    }
}

template <class T>
bool
forward_multiskiplist<T> :: search(const T& key) {

    return count_key(key);
}

template <class T>
void
forward_multiskiplist<T> :: insert(const T& key, int count) {
    try {
        if (count < 1) {
            throw 1;
        }
    } catch (...) {
        std::cerr << "Standard exception: insert negative number of keys\n";
        return;
    }

    int height, curr_index, old_jump;
    _node<T> *tmp, *node, *it;

    if (!search(key)) {
        ++num_elem;
        
        height = get_new_height();
        curr_index = 0;

        node = new _node<T>(key, height, count);
        it = head;

        //std::cout << "\n\n" << key << " get -> h: " << height << " not foud yet";

        for (int i = max_height - 1; i > -1; --i) {
            while (it->forward[i] && key > it->forward[i]->data) {
                curr_index += it->jump[i] + 1;
                it = it->forward[i];
            }

            index_path[i] = curr_index;
            path[i] = it;

            //std::cout << "adrese: " << head << ' ' << it << '\n';
        }

        tmp = path[0]->forward[0];
        path[0]->forward[0] = node;
        node->forward[0] = tmp;
            
        old_jump = path[0]->jump[0];
        path[0]->jump[0] = 0;
        node->jump[0] = old_jump;

        for (int i = 1; i < height; ++i) {
            tmp = path[i]->forward[i];
            path[i]->forward[i] = node;
            node->forward[i] = tmp;
            
            old_jump = path[i]->jump[i];
            path[i]->jump[i] = index_path[i - 1] - index_path[i] + path[i - 1]->jump[i - 1];
            node->jump[i] = (old_jump == JUMP_TO_NULL)? JUMP_TO_NULL: old_jump - path[i]->jump[i];
        }

        for (int i = height; i < max_height; ++i) {
            if (path[i]->jump[i] != JUMP_TO_NULL) {
                ++path[i]->jump[i];
            }
        }

        /*std::cout << "\npath: ";
        for (int i = max_height - 1; i > -1; --i) {
            if (path[i]) {
                std::cout << path[i]->data << ' ';
            }
        }
        //std::cout << "\ninde: ";
        for (int i = max_height - 1; i > -1; --i) {
            if (path[i]) {
                std::cout << index_path[i] << ' ';
            }
        }
        */

    } else {
        it = head;

        for (int i = max_height - 1; i > -1; --i) {
            while (it->forward[i] && key > it->forward[i]->data) {
                it = it->forward[i];
            }
        }

        it->forward[0]->count += count;
    }
}

template <class T>
void
forward_multiskiplist<T> :: erase(const T& key, int count) {
    try {
        if (count < 1) {
            throw 1;
        }
    } catch (...) {
        std::cerr << "Standard exception: erase negative number of keys\n";
        return;
    }

    //std::cout << "\n\n" << key << " deleted now";


    int get_count = count_key(key);
    _node<T> *tmp, *it = head;

    if (get_count < 1) {
        return;
    } else {
        for (int i = max_height - 1; i > -1; --i) {
            while (it->forward[i] && key > it->forward[i]->data) {
                it = it->forward[i];
            }

            path[i] = it;
        }

        it->forward[0]->count -= count;
        if (it->forward[0]->count < 1) {
            --num_elem;

            tmp = it->forward[0];
            //it->forward[0] = tmp->forward[0];
            //it->jump[0] = tmp->jump[0];

            for (int i = 0; i < max_height; ++i) {
                
                if (path[i]->forward[i] != tmp) {
                    if (path[i]->forward[i]) {
                        --path[i]->jump[i];
                    }
                } else {
                    path[i]->forward[i] = tmp->forward[i];

                    if (path[i]->forward[i]) {
                        path[i]->jump[i] += tmp->jump[i];
                    } else {
                        //std::cout << "\nlvl " << i << " ce plm";
                        path[i]->jump[i] = JUMP_TO_NULL;
                    }
                }
            }

            delete tmp;
        }
    }
}

template <class T>
const T&
forward_multiskiplist<T> :: operator[](int index) {
    try {
        if (index < 0 || num_elem <= index) {
            throw 1;
        }
    } catch (...) {
        std::cerr << "Standard exception: index outside the bounds\n";
    }

    ++index;
    _node<T> *it = head;
    for (int i = max_height - 1; i > -1; --i) {
        while (it->forward[i] && index >= it->jump[i] + 1) {
            index -= it->jump[i] + 1;
            it = it->forward[i];
        }
    }

    return it->data;
}

#endif // __SKIPLIST_H__

#include <fstream>
std::ifstream fin("heapuri.in");
std::ofstream fout("heapuri.out");

int main() {
 
    forward_multiskiplist<long long int> heap;
    long long int n, i, k, type, x, value[200003];
 
    fin >> n;
    for (i = k = 0; i < n; ++i) {
 
        fin >> type;

        if (type == 3) {
            fout << heap.head->forward[0]->data << '\n';
        } else {
            fin >> x;

            if (type == 1) {
                ++k;
                value[k] = x; 
                heap.insert(x);
            } else {
                heap.erase(value[x]);
            }
        }
    }
	return 0;
}