#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;
mt19937 gen(time(0));

int fr() {
    return uniform_int_distribution<int>(0, INT_MAX)(gen);
}

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

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

typedef Treap* Node;

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

void sz_recalc (Node t) {
    if (t == nullptr) return;
    t->sz = get_sz (t->left)
            + get_sz (t->right) + 1;
}

Node treap_merge (Node t1, Node t2) {
    if (t1 == nullptr) return t2;
    if (t2 == nullptr) return t1;

    if (t1->x > t2->x) {
        t1->right = treap_merge (t1->right, t2);
        sz_recalc (t1);
        return t1;
    }

    t2->left = treap_merge (t1, t2->left);
    sz_recalc (t2);
    return t2;
}

void treap_print (Node t) {
    if (t == nullptr) return;

    cout << "[";
    treap_print (t->left);
    cout << " (" << t->x << ", " << t->y
         << ", " << t->sz << ") ";
    treap_print (t->right);
    cout << "]";
}

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

    if (k <= get_sz (t->left)) {
        auto p = treap_split_k (t->left, k);
        t->left = p.second;
        sz_recalc (t);
        return {p.first, t};
    }

    auto p = treap_split_k (t->right,
                            k - get_sz(t->left) - 1);
    t->right = p.first;
    sz_recalc (t);
    return {t, p.second};
}

Node treap_insert_k (Node t0, int k, int y0) {
    auto p = treap_split_k (t0, k);
    Node t = new Treap (y0);
    return treap_merge(
        p.first,
        treap_merge (t, p.second)
    ); 
}

Node treap_find_k (Node t, int k) {
    if (t == nullptr) return nullptr;
    if (k == get_sz (t->left)) return t;
    if (k < get_sz (t->left)) return treap_find_k (t->left, k);
    return treap_find_k (t->right, k - get_sz(t->left) - 1);
}

int main ( ) {
    Node t0 = new Treap (0);
    for (int i=1; i<11; i++) t0 = treap_insert_k(t0, 0, i);
    treap_print(t0);  cout << endl;
    return 0;
}