#include <iostream>
#include <algorithm>
#include <vector>  #include <bits/stdc++.h>

using namespace std;

struct Treap {
    int x;  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, Treap* t1 = nullptr, Treap* t2 = nullptr) :
        x(x_), 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};
}


int random (int limit)
{
	return unsigned ((rand () << 15) ^ rand ()) % limit;
}


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

    if (random(l->sz + r->sz) < l->sz) {
        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) {
    pair <Node, Node> p = treap_split (t_to, x);
    Node t = new Treap (x);
    return (treap_merge (p.first, treap_merge (t, p.second)));
}


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;

    int n_ = treap_output (t->left);
    cout << t->x << " ";
    n_ = treap_output (t->right);

    return 0;
}


int main ( ) {
    Treap t = Treap (0);  Node t0 = &t;

    for (int i = 0; i<400; i++) t0 = treap_insert (t0, random(5000));

    treap_output (t0); cout << endl << t0->depth() << endl;

    return 0;
}