#include <iostream>
#include <algorithm>

using namespace std;


struct Treap {
    int x;  int y;  // int id of this node, int size of our subtree
    Treap* left;  Treap* right;

    Treap (int x_ = 0, int y_ = 0) :
        x(x_),  y(y_),
        left(nullptr),  right(nullptr)
    { }
};


pair <Treap*, Treap*> treap_split (Treap* t, int xs) {  // splitK
    if (t == nullptr) return {nullptr, nullptr};

    if (xs <= t->x) {  // key is to the left of the root
        pair <Treap*, Treap*> p = treap_split (t->left, xs);
        t->left = p.second;  // t->right does not change
        return {p.first, t};
    } else {
        pair <Treap*, Treap*> p = treap_split (t->right, xs);
        t->right = p.first;  // t->left does not change
        return {t, p.second};
    }
}


Treap* treap_merge (Treap* l, Treap* r) {
    if (l == nullptr) return r;
    if (r == nullptr) return l;

    if (l->y >= r->y) {
        l->right = treap_merge (l->right, r);
        return l;
    } else {
        r->left = treap_merge (l, r->left);
        return r;
    }
}


int treap_output (Treap* t) {
    if (t == nullptr) return 0;

    cout << "[";
    int n_ = treap_output (t->left);
    cout << " " << t->x << ", " << t->y << " ";
    n_ = treap_output (t->right);
    cout << "]";

    return 0;
}


// Treap it (xs, ys)
Treap* treap_insert (Treap* t, Treap* it) {
    int xs = it->x;

    pair <Treap*, Treap*> p = treap_split (t, xs);
    return treap_merge (p.first, treap_merge (it, p.second));
}


// keys are integer
// when splitting the key is in the right tree
Treap* treap_remove (Treap* t, int xs) {
    pair <Treap*, Treap*> p1 = treap_split (t, xs);
    pair <Treap*, Treap*> p2 = treap_split (p1.second, xs + 1);
    return treap_merge (p1.first, p2.second);
}


int main() {
    Treap t1 (2, 2);
    Treap t2 (0, 4);
    Treap t3 (1, 8);
    Treap t4 (1, 3);

    Treap* tt1 = treap_insert (&t1, &t2);
    Treap* tt2 = treap_insert (tt1, &t3);
    Treap* tt3 = treap_insert (tt2, &t4);

    Treap* tt = treap_remove (tt3, 1);
    int n = treap_output (tt);

    return 0;
}