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

mt19937 rng;
/// лучше rand

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

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

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

struct treap_manager
{
	vector<node> v;

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

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

		if (v[t].x >= x0)
		{
			auto [l, r] = split(v[t].l, x0);
			///pair<int, int> p = split(v[t].l, x0);
			///int l = p.first, r = p.second;
			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 (int l, int r) /// не const
	{
		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;
		}
	}

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

	void remove (int &root, const int x)
	{
		auto [l, temp] = split(root, x);
		auto [m, r] = split(temp, x + 1);
		/// утечка памяти!
		root = merge(l, r);
	}

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

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.remove(root, 2);
	info.print_with_newline(root);
	info.remove(root, 2);
	info.print_with_newline(root);
}