#include <iostream>
#include <algorithm>

using namespace std;


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

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

    int left_size () {
        if (left == nullptr) return 0;
        else return left->s;
    }

    int right_size () {                  // THE BUG WAS HERE
        if (right == nullptr) return 0;  // I copypasted the code
        else return right->s;            // without changing left to right
    }

    void recalc () {
        s = left_size () + right_size () + 1;
    }
};


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
        t->recalc ();
        return {p.first, t};
    } else {
        pair <Treap*, Treap*> p = treap_split (t->right, xs);
        t->right = p.first;  // t->left does not change
        t->recalc ();
        return {t, p.second};
    }
}


pair <Treap*, Treap*> treap_splitK (Treap* t, int k) {
    if (t == nullptr && k == 0) return {nullptr, nullptr};
    if (t == nullptr && k != 0)
        throw length_error ("non null split size for empty treap");

    if (k == t->s) return {t, nullptr};
    if (k == 0) return {nullptr, t};
    if (k < 0 || k > t->s)
        throw out_of_range ("split index out of limits");

    if (k <= t->left_size ()) {
        pair <Treap*, Treap*> p = treap_splitK (t->left, k);
        t->left = p.second;  t->recalc ();
        return {p.first, t};
    } else {
        pair <Treap*, Treap*> p = treap_splitK (t->right,
                                                k - t->left_size() - 1);
        t->right = p.first;  t->recalc ();
        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);
        l->recalc ();
        return l;
    } else {
        r->left = treap_merge (l, r->left);
        r->recalc ();
        return r;
    }
}


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

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

    return 0;
}


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);
    int n = treap_output (tt3);  cout << endl;

    pair <Treap*, Treap*> p = treap_splitK (tt3, 2);

    n = treap_output(p.first);  cout << endl;
    n = treap_output(p.second);

    return 0;
}