#include <iostream>
#include <random>
#include <chrono>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node
{
	int x;
	int y;
	Node* left;
	Node* right;

	Node(int x_)
	{
		left = nullptr;
		right = nullptr;
		x = x_;
		y = rng(); 
	}
};


pair<Node*, Node*> TreapSplit (Node* t, int x)
{
	if (t == nullptr)
		return { nullptr, nullptr };
	if (t->x >= x)
	{
		auto temp = TreapSplit(t->left, x);
		t->left = temp.second;
		return { temp.first, t };
	}
	else
	{
		auto temp = TreapSplit(t->right, x);
		t->right = temp.first;
		return{ t, temp.second };
	}
}

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

	if (r->y >= l->y)
	{
		r->left = TreapMerge(l, r->left);
		return r;
	}
	else
	{
		l->right = TreapMerge(l->right, r);
		return l;
	}
}

void TreapDelete(Node* t)
{
	if (t == nullptr)
		return;
	TreapDelete(t->left);
	TreapDelete(t->right);
	delete t;
}


Node* TreapInsert(Node* t, int x)
{
	Node* nodex = new Node(x);
	auto temp = TreapSplit(t, x);
	return TreapMerge(temp.first, TreapMerge(nodex, temp.second));
}

Node* TreapRemove(Node* t, int x)
{
	auto temp = TreapSplit(t, x);
	auto temp2 = TreapSplit(temp.second, x + 1);
	TreapDelete(temp2.first);
	return TreapMerge(temp.first, temp2.second); 
}

void TreapOutput(Node* t, int depth)
{
	if (t == nullptr)
		return;
	TreapOutput(t->left, depth + 1);
	for (int i = 0; i < depth; i++)
	{
		cout << " ";
	}
	cout << t->x << endl;
	TreapOutput(t->right, depth + 1);
}



int main()
{
	int size = 50;
	Node* root = new Node(rng()% 100);
	for (int i = 0; i < size; i++)
	{
		root = TreapInsert(root, rng() % 100);
	}
	TreapOutput(root, 0);
	return 0;
}