treap

#include <ctime>
#include <cstdio>
#include <cstdlib>

#include <algorithm>

#define GET_CHILD(P, SIDE) ((SIDE) ? (P)->r : (P)->l)

// #define NO_ROTATION
// #define DEBUG_MODE

using namespace std;

struct node {
    int d, rnd, sz, cnt;
    node *l, *r;
};

const int N = 100010;
int ans;
node* root;
node* insertion_needed;

int fast_rand();
node* create(int x);
void insert(node*& p, int x);
void insert(node*& p, node* q);
void update(node* p);
void rotate(node*& p, bool f);
void del(node*& p, int x);
void pre(node* p, int x);
void post(node* p, int x);
int get_rank(node* p, int x);
int get_x(node* p, int r);
void debug(node* p);
void print_tree(node* p);

int main() {
    int n, o, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &o, &x);
        switch (o) {
        case 1:
            insert(root, x);
            break;
        case 2:
            insertion_needed = NULL;
            del(root, x);
            if (insertion_needed)
                insert(root, insertion_needed);
            break;
        case 3:
            printf("%d\n", get_rank(root, x));
            break;
        case 4:
            printf("%d\n", get_x(root, x));
            break;
        case 5:
            ans = -1e9;
            pre(root, x);
            printf("%d\n", ans);
            break;
        case 6:
            ans = 1e9;
            post(root, x);
            printf("%d\n", ans);
            break;
        default: break;
        }
#ifdef DEBUG_MODE
        debug(root);
#endif
    }
    return 0;
}

inline node* create(int x) {
    static node pool[N];
    static int cnt = -1;
    node* ret = pool + ++cnt;
    ret->d = x;
    ret->rnd = fast_rand();
    ret->sz = ret->cnt = 1;
    return ret;
}

inline int fast_rand() {
    static int x = time(NULL) << 4, y = time(NULL) >> 2, z = time(NULL);
    int t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;
    t = x;
    x = y;
    y = z;
    z = t ^ x ^ y;
    return z;
}

void insert(node*& p, int x) {
    if (!p) {
        p = create(x);
        return;
    }
    ++p->cnt;
    if (p->d == x) {
        ++p->sz;
        return;
    }
    if (p->d > x) {
        insert(p->l, x);
        if (p->l->rnd < p->rnd)
            rotate(p, false);
    } else {
        insert(p->r, x);
        if (p->r->rnd < p->rnd)
            rotate(p, true);
    }
    update(p);
}

void insert(node*& p, node* q) {
    if (!p) {
        p = q;
        return;
    }
    ++p->cnt;
    if (p->d > q->d) {
        insert(p->l, q);
        if (p->l->rnd < p->rnd)
            rotate(p, false);
    } else {
        insert(p->r, q);
        if (p->r->rnd < p->rnd)
            rotate(p, true);
    }
    update(p);
}

inline void update(node* p) {
    p->cnt = p->sz;
    if (p->l)
        p->cnt += p->l->cnt;
    if (p->r)
        p->cnt += p->r->cnt;
}

inline void rotate(node*& p, bool f) {
#ifndef NO_ROTATION
    node* son = GET_CHILD(p, f);
    GET_CHILD(p, f) = GET_CHILD(son, !f);
    GET_CHILD(son, !f) = p;
    update(p);
    p = son;
#endif
    update(p);
}

void del(node*& p, int x) {
    if (p->d == x) {
        if (--p->sz)
            --p->cnt;
        else {
            if (p->l) {
                insert(insertion_needed, p->l);
                p->l = NULL;
            }
            if (p->r) {
                insert(insertion_needed, p->r);
                p->r = NULL;
            }
            p = NULL;
        }
        return;
    }
    if (p->d > x)
        del(p->l, x);
    else
        del(p->r, x);
    update(p);
}

int get_x(node* p, int r) {
    if (p->l) {
        if (p->l->cnt >= r)
            return get_x(p->l, r);
        r -= p->l->cnt;
    }
    if (r <= p->sz)
        return p->d;
    return get_x(p->r, r - p->sz);
}

int get_rank(node* p, int x) {
    int ret = 0;
    if (p->d > x)
        return get_rank(p->l, x);
    if (p->l)
        ret += p->l->cnt;
    if (p->d == x)
        return ret + 1;
    return ret + p->sz + get_rank(p->r, x);
}

inline void pre(node* p, int x) {
    while (p) {
        if (p->d < x) {
            ans = max(p->d, ans);
            p = p->r;
        } else
            p = p->l;
    }
}

inline void post(node* p, int x) {
    while (p) {
        if (p->d > x) {
            ans = min(p->d, ans);
            p = p->l;
        } else
            p = p->r;
    }
}

void debug(node* p) {
    if (p->l)
        debug(p->l);
    if (p->r)
        debug(p->r);
    int x = p->cnt;
    update(p);
    if (p->cnt != x) {
        print_tree(root);
        fprintf(stderr, "\nERROR!\n");
        exit(0);
    }
}

void print_tree(node* p) {
    if (!p)
        return;
    fputc('(', stderr);
    print_tree(p->l);
    fprintf(stderr, "%d", p->d);
    print_tree(p->r);
    fputc(')', stderr);
}