Cartesian

#include <bits/stdc++.h>
using namespace std;

const int MAX_CNT = 1000000;

struct Node
{
  int key, y;
  int left, right;
  int cnt;

  Node(int x = 0): key(x), y(0), left(0), right(0), cnt(1) {}
  void gen_y()
  {
    y = (rand() << 15) | rand();
  }
};

Node nodes[MAX_CNT + 1];
queue<int> free_nodes;

void init()
{
  for(int i=1; i<=MAX_CNT; ++i) free_nodes.push(i);
}

int alloc_node()
{
  if (free_nodes.size() == 0) assert(false);
  int i = free_nodes.front();
  free_nodes.pop();
  return i;
}

void free_node(int i)
{
  free_nodes.push(i);
}

int root_id = 0; // id of root node

// get count of nodes in tree
int get_cnt(const int & root)
{
  if (root == 0) return 0;
  return nodes[root].cnt;
}

// change info about count
void update_cnt(const int & root)
{
  if (root == 0) return;
  int left_cnt = get_cnt(nodes[root].left);
  int right_cnt = get_cnt(nodes[root].right);
  nodes[root].cnt = left_cnt + right_cnt + 1;
}

// return true if node with key in tree root
bool exists(const int & root, int key)
{
  if ( root == 0 ) return false;
  if ( nodes[root].key == key ) return true;
  if ( key < nodes[root].key )
    return exists( nodes[root].left, key );
  return exists( nodes[root].right, key );
}

// split tree by key and return two roots
// [ ... k] | (k ... ]
pair<int, int> split(const int & root, int key)
{
  if ( root == 0 ) return {0, 0};
  if ( key <= nodes[root].key )
  {
    auto res = split( nodes[root].left, key ); // res.first => L, res.second => R, nodes[node] => X
    nodes[root].left = res.second;
    update_cnt(root);
    return {res.first, root};
  }
  else
  {
    auto res = split( nodes[root].right, key );
    nodes[root].right = res.first;
    update_cnt(root);
    return {root, res.second};
  }
}

// merge two trees and return root
int merge(const int & root1, const int & root2)
{
  if ( root1 == 0 ) return root2;
  if ( root2 == 0 ) return root1;
  if ( nodes[root1].y <= nodes[root2].y )
  {
     nodes[root1].right = merge( nodes[root1].right, root2 );
     update_cnt(root1);
     return root1;
  }
  else
  {
    nodes[root2].left = merge( root1, nodes[root2].left );
    update_cnt(root2);
    return root2;
  }
}

int insert( int & root, const int & key )
{
  if ( exists(root, key) ) return root;
  auto res = split(root, key);
  int new_node = alloc_node();
  nodes[new_node].key = key;
  nodes[new_node].gen_y();
  root = merge( merge(res.first, new_node), res.second );
  return root;
}

int erase(int & root, const int & key)
{
  if( !exists(root, key) ) return root;
  auto res1 = split( root, key );
  auto res2 = split( res1.first, key-1 );
  free_node( res2.second );
  root = merge(res2.first, res1.second);
  return root;
}

int depth(const int & root)
{
  if (root == 0) return 0;
  int left_depth = depth(nodes[root].left);
  int right_depth = depth(nodes[root].right);
  return max(left_depth, right_depth) + 1;
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // freopen("INPUT.TXT", "r", stdin);
  init();
  int n = MAX_CNT;
  srand(time(0));
  for(int i=0; i<n; ++i)
  {
    int x = (rand() << 15) | rand();
    root_id = insert(root_id, x);
  }

  cout << depth(root_id) << " " << nodes[root_id].cnt;
}