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

mt19937 rng(450);

struct node
{
	int l, r;
	int x, y;

	node() : l(-1), r(-1), x(-1), y(-1) {}

	node(const int x0) : l(-1), r(-1), x(x0), y(rng()) {}
};

struct treap_manager
{
	vector<node> v;

	pair<int, int> split (const int t, const int x0)
	{
		if (t == -1)
			return pair<int, int>(-1, -1);

		if (v[t].x >= x0)
		{
			///int l, r;
			///pair<int, int> p = split(v[t].l, x0);
			///l = p.first; r = p.second;
			auto [l, r] = split(v[t].l, x0);

			v[t].l = r;
			return pair<int, int>(l, t);
		}
		else
		{
			auto [l, r] = split(v[t].r, x0);
			v[t].r = l;
			return pair<int, int>(t, r);
		}
	}

	int merge (const int l, const int r)
	{
		if (l == -1)
			return r;
		if (r == -1)
			return l;

		if (v[l].y > v[r].y)
		{
			v[l].r = merge(v[l].r, r);
			return l;
		}
		else
		{
			v[r].l = merge(l, v[r].l);
			return r;
		}
	}

	int newnode (const int x)
	{
		v.push_back(node(x));
		return int(v.size()) - 1;
	}

	void print_with_newline (const int t)
	{
		print_order(t);
		cout << endl;
	}


	void print_order (const int t)
	{
		if (t == -1)
			return;

		print_order(v[t].l);
		cout << v[t].x << " ";
		print_order(v[t].r);
	}

	void insert (int &root, const int x)
	{
		const int m = newnode(x);
		auto [l, r] = split(root, x);
	 	root = merge(merge(l, m), r);
	}

	void erase (int &root, const int x)
	{
		auto [l, temp] = split(root, x);
		auto [m, r] = split(temp, x + 1);
		root = merge(l, r);
	}
};

int main()
{
	treap_manager info;

	int root = -1;
	info.insert(root, 3);
	info.print_with_newline(root);
	info.insert(root, -1);
	info.print_with_newline(root);
	info.insert(root, 4);
	info.print_with_newline(root);
	info.insert(root, 2);
	info.print_with_newline(root);
	info.erase(root, 2);
	info.print_with_newline(root);
}