#include <iostream>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
mt19937 gen(time(0));

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

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

typedef Treap* Node;

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

// returns a random number within 0..limit
int random (int limit) {
    return uniform_int_distribution<int>(0, limit-1)(gen);
}
/* When I need an event with probability p/q:
if random(size_left + size_right) < size_right
*/

/* Size recalculation can not be done by just
subtracting / adding smth to the current size,
a separate function is needed. */
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 (random (t1->sz + t2->sz) < t1->sz) {
        // t1 is selected as root
        t1->right = treap_merge (t1->right, t2);
        sz_recalc (t1);
        return t1;
    }

    // t2 is selected as root
    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->sz << ") ";
    treap_print (t->right);
    cout << "]";
}

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);
}

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 x0, int k) {
    auto p = treap_split_k (t0, k);
    Node t = new Treap (x0);
    return treap_merge(
        p.first,
        treap_merge (t, p.second)
    ); 
}

int depth (Node t) {
    if (t==nullptr) return 0;
    return max (depth (t->left), depth (t->right)) + 1;
}

int main ( ) {
    Node t0 = new Treap (0);

    for (int x=1; x<1000; x++)
        t0 = treap_insert_k (t0, x, random (t0->sz));
    treap_print (t0);  cout << endl;
    cout << depth (t0);

    // auto p = treap_split_k (t0, 6);
    // treap_print (p.first); cout << endl;
    // treap_print(p.second);

    return 0;
}