<snippet>
    <content><![CDATA[
template<typename T>
class Treap {
    struct Node {
        int l, r, key, sz;
        T v;
    };

    Node *tr;
    int root, idx;
  public:

    ~Treap() {
        delete[] tr;
    }

    Treap(int n) : root(0), idx(0) {
        tr = new Node[n + 10]();
    }

    void pushup(int u) {
        tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + 1;
    }

    int add(T v) {
        ++idx;
        tr[idx].key = rand(), tr[idx].sz = 1, tr[idx].v = v;
        return idx;
    }

    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (tr[x].key > tr[y].key) {
            tr[x].r = merge(tr[x].r, y);
            pushup(x);
            return x;
        }
        else {
            tr[y].l = merge(x, tr[y].l);
            pushup(y);
            return y;
        }
    }

    void split(int u, T val, int &x, int &y) {
        if (!u) return x = y = 0, void();
        if (tr[u].v <= val)
            x = u, split(tr[u].r, val, tr[u].r, y);
        else
            y = u, split(tr[u].l, val, x, tr[u].l);
        pushup(u);
    }

    void insert(T v) {
        int x, y;
        split(root, v, x, y);
        root = merge(x, merge(add(v), y));
    }

    void remove(T v) {
        int x, y, z;
        split(root, v, x, z);
        split(x, v - 1, x, y);
        y = merge(tr[y].l, tr[y].r);
        root = merge(merge(x, y), z);
    }

    int val_rk(T v) {
        int x, y;
        split(root, v - 1, x, y);
        int res = tr[x].sz + 1;
        root = merge(x, y);
        return res;
    }

    T rk_val(int k) {
        int u = root;
        while (u) {
            if (tr[tr[u].l].sz + 1 == k) return tr[u].v;
            else if (tr[tr[u].l].sz >= k) u = tr[u].l;
            else k -= tr[tr[u].l].sz + 1, u = tr[u].r;
        }
        return -1;
    }

    T get_prev(T v) {
        int x, y;
        split(root, v - 1, x, y);
        int u = x;
        while (tr[u].r) u = tr[u].r;
        int res = tr[u].v;
        root = merge(x, y);
        return res;
    }

    T get_next(T v) {
        int x, y;
        split(root, v, x, y);
        int u = y;
        while (tr[u].l) u = tr[u].l;
        int res = tr[u].v;
        root = merge(x, y);
        return res;
    }
};
]]></content>
    <!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
    <!-- <tabTrigger>hello</tabTrigger> -->
    <!-- Optional: Set a scope to limit where the snippet will trigger -->
    <!-- <scope>source.python</scope> -->
</snippet>