struct Treap {
    static Treap *null;
    int x, y;
    int val, sum;
    Treap *l, *r;
    Treap() {
        x = y = val = sum = 0;
        l = r = this;
    }
    Treap(int x_, int v) {
        x = x_;
        val = sum = v;
        y = rand();
        l = r = null;
    }
    void recount() {
        sum = val + l->sum + r->sum;
    }
};

Treap* Treap::null = new Treap();

void split(Treap *t, int x, Treap *&l, Treap *&r) {
    if(t == Treap::null) {
        l = r = t;
        return;
    }
    if(t->x < x) {
        l = t;
        split(l->r, x, l->r, r);
    } else {
        r = t;
        split(r->l, x, l, r->l);
    }
    t->recount();
}

Treap* merge(Treap *l, Treap *r) {
    if(l == Treap::null)
        return r;
    if(r == Treap::null)
        return l;
    if(l->y > r->y) {
        l->r = merge(l->r, r);
        l->recount();
        return l;
    } else {
        r->l = merge(l, r->l);
        r->recount();
        return r;
    }
}