treap2

#include <climits>
#include <cstdio>
#include <ctime>

#include <algorithm>

#define GET_CH(P, F) ((F) ? (P)->rs : (P)->ls)
#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

struct node {
    int x, cnt, rnd;
    node *ls, *rs;
};

const int N = 300010;

int n;
node *res1, *res2, *root;

node* create(int x);
int get_cnt(node* p);
int ran(node* p, int x);
int get(node* p, int rk);
int prev(node* p, int x);
int post(node* p, int x);
void update(node* p);
void debug_order(node* p);
void insert(node*& p, node* q);
void rotate(node*& p, bool f);
void p_remove(node*& p, int x);
void remove(node*& p, int x);

int main() {
    int op, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &op, &x);
        switch (op) {
        case 0:
            insert(root, create(x));
            break;
        case 1:
            remove(root, x);
            break;
        case 2:
            printf("%d\n", get(root, x));
            break;
        case 3:
            printf("%d\n", ran(root, x));
            break;
        case 4:
            x = prev(root, x);
            printf("%d\n", x == INT_MIN ? -1 : x);
            break;
        case 5:
            x = post(root, x);
            printf("%d\n", x == INT_MAX ? -1 : x);
            break;
        }
    }
    return 0;
}

void debug_order(node* root) {
    if (!root)
        return;
    LOG("(");
    debug_order(root->ls);
    LOG(")<-%d->(", root->x);
    debug_order(root->rs);
    LOG(")");
}

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

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

inline void rotate(node*& p, bool f) {
    node* son = GET_CH(p, f);
    GET_CH(p, f) = GET_CH(son, !f);
    GET_CH(son, !f) = p;
    update(p);
    p = son;
    update(p);
}

inline int get_cnt(node* p)
{ return p ? p->cnt : 0; }

inline void update(node* p)
{ p->cnt = 1 + get_cnt(p->ls) + get_cnt(p->rs); }

void insert(node*& p, node* q) {
    if (!p) {
        p = q;
        return;
    }
    if (q->x < p->x) {
        insert(p->ls, q);
        update(p);
        if (p->ls->rnd < p->rnd)
            rotate(p, 0);
    } else {
        insert(p->rs, q);
        update(p);
        if (p->rs->rnd < p->rnd)
            rotate(p, 1);
    }
}

inline void remove(node*& p, int x) {
    p_remove(p, x);
    if (res1)
        insert(p, res1);
    if (res2)
        insert(p, res2);
}

void p_remove(node*& p, int x) {
    if (p->x == x) {
        res1 = p->ls;
        res2 = p->rs;
        p = NULL;
        return;
    }
    if (x < p->x)
        p_remove(p->ls, x);
    else
        p_remove(p->rs, x);
    update(p);
}

inline int ran(node* p, int x) {
    int ret = 0;
    while (p) {
        if (x <= p->x)
            p = p->ls;
        else {
            ret += get_cnt(p->ls) + 1;
            p = p->rs;
        }
    }
    return ret;
}

int get(node* p, int rk) {
    while (p) {
        if (rk == get_cnt(p->ls) + 1)
            return p->x;
        if (rk <= get_cnt(p->ls))
            p = p->ls;
        else {
            rk -= get_cnt(p->ls) + 1;
            p = p->rs;
        }
    }
    return 0;
}

inline int prev(node* p, int x) {
    int ret = INT_MIN;
    while (p)
        if (p->x < x) {
            ret = max(ret, p->x);
            p = p->rs;
        } else
            p = p->ls;
    return ret;
}

inline int post(node* p, int x) {
    int ret = INT_MAX;
    while (p)
        if (p->x > x) {
            ret = min(ret, p->x);
            p = p->ls;
        } else
            p = p->rs;
    return ret;
}