#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Treap {
    int x;  int y;  int sz;
    Treap* left;  Treap* right;

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

typedef Treap* Node;


pair <Node, Node> treap_split (Node t, int x0) {
    // need to recalc the size!!
    if (t == nullptr) return {nullptr, nullptr};

    if (x0 <= t->x) {
        pair <Node, Node> p = treap_split (t->left, x0);
        t->left = p.second;
        return {p.first, t};
    }

    pair <Node, Node> p = treap_split (t->right, x0);
    t->right = p.first;
    return {t, p.second};
}


Node treap_merge (Node l, Node r) {
    // need to recalc the size!!
    if (l == nullptr) return r;  if (r == nullptr) return l;

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

    r->left = treap_merge (l, r->left);
    return r;
}


Node treap_insert (Node t_to, int x, int y) {
    pair <Node, Node> p = treap_split (t_to, x);
    Node t = new Treap (x, y);
    return (treap_merge (p.first, treap_merge (t, p.second)));
}


Node treap_insert_one_log (Node t_to, int x, int y) {
    // спускаемся в дереве, пока потомок
    // со стороны (x,y) не станет ниже y
    Node t = t_to;
    while (true) {
        if (t_to->y > y) {
            if (t_to->x == x)
                return t_to;
            if (t_to->x > x) { }
        }
    }
}


int treap_output (Node 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;
}


int main ( ) {
    Treap t = Treap (-6, -7);
    Node t0 = &t;

    vector <pair <int, int>> v =
        {{-4,4}, {-3,-1}, {-1,6}, {1,2},
         {2,10}, {3,-5}, {6,0}};

    for (auto p : v) {
        t0 = treap_insert (t0, p.first, p.second);
    }

    treap_output(t0);

    return 0;
}