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

using namespace std;

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

    void recalc () {
        sz = 1;  if (left != nullptr) {sz += left->sz;}
        if (right != nullptr) {sz += right->sz;}
    }

    int depth () {
        int ld = 0, rd = 0;
        if (left != nullptr) {ld = left->depth();}
        if (right != nullptr) {rd = right->depth();}
        if (ld > rd) {return ld+1;} else {return rd+1;}
    }

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

typedef Treap* Node;


int get_size (Node t) {
    if (t == nullptr) return 0;
    return t->sz;
}


pair <Node, Node> treap_split (Node t, int x0) {
    if (t == nullptr) return {nullptr, nullptr};

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

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


pair <Node, Node> treap_split_k (Node t, int k) {
    if (t == nullptr) return {nullptr, nullptr};

    if (get_size(t->left) >= k) {
        pair <Node, Node> p = treap_split_k (t->left, k);
        t->left = p.second;  t->recalc();
        return {p.first, t};
    }

    pair <Node, Node> p = treap_split_k (t->right, k-1-get_size(t->left));
    t->right = p.first;  t->recalc();
    return {t, p.second};
}


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

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

    r->left = treap_merge (l, r->left);
    r->recalc();  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_fast_insert (Node t_to, int x, int y) {
    if (t_to == nullptr) {
        Node t_out = new Treap (x, y);
        return t_out;
    }

    if (t_to->y > y) {
        if (t_to->x > x)
            t_to->left = treap_fast_insert(t_to->left, x, y);
        else if (t_to->x < x)
            t_to->right = treap_fast_insert(t_to->right, x, y);

        t_to->recalc();  return t_to;
    }

    auto p = treap_split(t_to, x);
    Node t_out = new Treap (x, y, p.first, p.second);
    t_out->recalc();  return t_out;
}


bool treap_find (Node t, int x) {
  if (t == nullptr) return false;
  if (t->x == x) return true;
  if (t->x < x) return treap_find(t->right, x);
  return treap_find(t->left, x);
}


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

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

    return 0;
}


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

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

    for (auto p : v)
        t0 = treap_fast_insert (t0, p.first, p.second);

    treap_output(t0);  cout << endl;

    auto p = treap_split_k (t0, 3);

    treap_output(p.first); cout << endl;
    treap_output(p.second); cout << endl;
    cout << treap_find(t0, 3) << " " << treap_find(t0, 0) << endl;

    return 0;
}