#include <cstdio>
#include <cstring>
#include <climits>
#include <set>
#include <algorithm>
const int MAX_N = 100000;
const int MAX_VAL = 1e9;
struct Spaly {
    struct Node {
        Node *fa, *c[2], *pathFa;
        Node *lc, *rc, *par;
        int size;
        Node() : fa(NULL), pathFa(NULL), lc(NULL), rc(NULL), par(NULL), size(1) { c[0] = c[1] = NULL; }
        void maintain() {
            size = (c[0] ? c[0]->size : 0) + (c[1] ? c[1]->size : 0) + 1;
        }
        int relation() {
            return this == fa->c[1];
        }
        void rotate() {
            Node *old = fa;
            int x = relation();
            std::swap(fa->pathFa, pathFa);
            fa = old->fa;
            if (old->fa) old->fa->c[old->relation()] = this;
            old->c[x] = c[x ^ 1];
            if (c[x ^ 1]) c[x ^ 1]->fa = old;
            c[x ^ 1] = old;
            old->fa = this;
            old->maintain(), maintain();
        }
        void splay() {
            while (fa) {
                if (!fa->fa) rotate();
                else if (fa->relation() == relation()) fa->rotate(), rotate();
                else rotate(), rotate();
            }
        }
        void expose() {
            splay();
            if (c[1]) {
                std::swap(c[1]->fa, c[1]->pathFa);
                c[1] = NULL;
            }
            maintain();
        }
        bool splice() {
            splay();
            if (!pathFa) return false;
            pathFa->expose();
            pathFa->c[1] = this;
            std::swap(fa, pathFa);
            fa->maintain();
            return true;
        }
        void access() {
            expose();
            while (splice());
        }
        int depth() {
            access();
            splay();
            return size;
        }
    } N[MAX_N], *root;
    void link(Node *u, Node *par) {
        u->access();
        u->splay();
        u->pathFa = par;
    }
    void cut(Node *u) {
        u->access();
        u->splay();
        if (u->c[0]) u->c[0]->fa = NULL;
        u->c[0] = NULL;
    }
/*	Node *findRoot(Node *v) {
        v->access();
        v->splay();
        while (v->c[0]) v = v->c[0];
        return v;
    } */
} spaly;
int _end = 0;
struct SetNode {
    int val;
    Spaly::Node *v;
    SetNode(int val, Spaly::Node *v) : val(val), v(v) {}
    bool operator<(const SetNode &other) const {
        return val < other.val;
    }
};
std::set<SetNode> set;
inline int spalyMax() {
    std::set<SetNode>::const_iterator it = set.end();
    it--;
    int ans = it->v->depth();
    if (ans == 1) return ans;
    if (it->v->lc && it->v->par) {
//		Spaly::Node *spaly.root = spaly.findRoot(it->v);
        spaly.cut(it->v->lc);
        spaly.cut(it->v);
        spaly.link(it->v->lc, it->v->par);
        it->v->par->rc = it->v->lc;
        it->v->lc->par = it->v->par;
        it->v->lc = NULL;
        it->v->par = NULL;
        spaly.link(spaly.root, it->v);
        it->v->lc = spaly.root;
        spaly.root->par = it->v;
    } else if (it->v->par) {
//		Spaly::Node *spaly.root = spaly.findRoot(it->v);
        spaly.cut(it->v);
        it->v->par->rc = NULL;
        it->v->par = NULL;
        spaly.link(spaly.root, it->v);
        spaly.root->par = it->v;
        it->v->lc = spaly.root;
    }
    spaly.root = it->v;
    return ans;
}
inline int spalyMin() {
    std::set<SetNode>::const_iterator it = set.begin();
    int ans = it->v->depth();
    if (ans == 1) return ans;
    if (it->v->rc && it->v->par) {
//		Spaly::Node *spaly.root = spaly.findRoot(it->v);
        spaly.cut(it->v->rc);
        spaly.cut(it->v);
        spaly.link(it->v->rc, it->v->par);
        it->v->rc->par = it->v->par;
        it->v->par->lc = it->v->rc;
        it->v->rc = NULL;
        it->v->par = NULL;
        spaly.link(spaly.root, it->v);
        spaly.root->par = it->v;
        it->v->rc = spaly.root;
    } else if (it->v->par) {
//		Spaly::Node *spaly.root = spaly.findRoot(it->v);
        spaly.cut(it->v);
        it->v->par->lc = NULL;
        it->v->par = NULL;
        spaly.link(spaly.root, it->v);
        spaly.root->par = it->v;
        it->v->rc = spaly.root;
    }
    spaly.root = it->v;
    return ans;
}
inline int delMax() {
    std::set<SetNode>::const_iterator it = set.end();
    it--;
    int ans = spalyMax();
    if (it->v->lc) spaly.cut(it->v->lc), it->v->lc->par = NULL, spaly.root = it->v->lc;
    set.erase(it);
    return ans;
}
inline int delMin() {
    std::set<SetNode>::const_iterator it = set.begin();
    int ans = spalyMin();
    if (it->v->rc) spaly.cut(it->v->rc), it->v->rc->par = NULL, spaly.root = it->v->rc;
    set.erase(it);
    return ans;
}
inline int insert(int val) {
    SetNode v(val, &spaly.N[_end++]);
    if (set.empty()) return set.insert(v), spaly.root = v.v, 1;
    std::set<SetNode>::const_iterator suc = set.lower_bound(v), pre = suc;
    if (suc == set.end()) {
        pre--;
        spaly.link(v.v, pre->v);
        v.v->par = pre->v;
        pre->v->rc = v.v;
    } else if (suc == set.begin()) {
        spaly.link(v.v, suc->v);
        v.v->par = suc->v;
        suc->v->lc = v.v;
    } else {
        pre--;
        if (pre->v->depth() > suc->v->depth()) {
            spaly.link(v.v, pre->v);
            v.v->par = pre->v;
            pre->v->rc = v.v;
        } else {
            spaly.link(v.v, suc->v);
            v.v->par = suc->v;
            suc->v->lc = v.v;
        }
    }
    set.insert(v);
    return v.v->depth();
}
int main() {
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int cmd;
        scanf("%d", &cmd);
        if (cmd == 1) {
            int key;
            scanf("%d", &key);
            printf("%d\n", insert(key));
        } else if (cmd == 2) {
            printf("%d\n", spalyMin());
        } else if (cmd == 3) {
            printf("%d\n", spalyMax());
        } else if (cmd == 4) {
            printf("%d\n", delMin());
        } else if (cmd == 5) {
            printf("%d\n", delMax());
        }
    }
    return 0;
}