// basic treap: split, merge, insert, +remove
#include <iostream>
#include <random>
#include <utility>
using namespace std;

//random_device dev;
//mt19937 gen (dev ());
mt19937 gen (1234567890);

struct Node;
using PNode = Node *;
struct Node
{
	int x;
	int y;
	PNode left;
	PNode right;

	Node (int x_)
	{
		x = x_;
		y = uniform_int_distribution <int> (0, 1E9) (gen);
		left = nullptr;
		right = nullptr;
	}
};

bool tFind (PNode t, int x)
{
	if (t == nullptr)
	{
		return false;
	}
	if (t -> x == x)
	{
		return true;
	}
	if (t -> x < x)
	{
		return tFind (t -> right, x);
	}
	else
	{
		return tFind (t -> left, x);
	}
}

void tOutputRecur (PNode t)
{
	if (t == nullptr)
	{
		return;
	}
	cout << "(";
	tOutputRecur (t -> left);
	cout << t -> x;
	tOutputRecur (t -> right);
	cout << ")";
}

void tOutput (PNode t)
{
	tOutputRecur (t);
	cout << endl;
}

pair <PNode, PNode> tSplit (PNode t, int x)
{ // first: < x ; second: >= x
	if (t == nullptr)
	{
		return {nullptr, nullptr};
	}
	if (t -> x < x)
	{
		auto temp = tSplit (t -> right, x);
		t -> right = temp.first;
		return {t, temp.second};
	}
	else
	{
		auto temp = tSplit (t -> left, x);
		t -> left = temp.second;
		return {temp.first, t};
	}
}

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

PNode tInsert (PNode t, int x)
{
	auto temp = tSplit (t, x);
	auto v = new Node (x);
	// (temp.first | v) | temp.second
	auto half = tMerge (temp.first, v);
	return tMerge (half, temp.second);
}

void tDelete (PNode t)
{
	if (t == nullptr)
	{
		return;
	}
	tDelete (t -> left);
	tDelete (t -> right);
	delete t;
}

PNode tRemove (PNode t, int x)
{
	auto one = tSplit (t, x);
	auto two = tSplit (one.second, x + 1);
	// TODO one.first | two.first | two.second
	tDelete (two.first);
	return tMerge (one.first, two.second);
}

int main ()
{
	int const size = 1000000; // test for speed
	PNode root = nullptr;
	tOutput (root);
	for (int i = 1; i <= size * 2; i += 2)
	{
		root = tInsert (root, i);
//		tOutput (root); // set size to 10 and then uncomment
	}
	for (int i = 1; i <= size; i++)
	{
//		cout << tFind (root, i); // set size to 10 and then uncomment
		tFind (root, i);
	}
	for (int i = 1; i <= size * 2; i += 2)
	{
		if (size * 2 - i == 111) tOutput (root);
		root = tRemove (root, i);
//		tOutput (root); // set size to 10 and then uncomment
		if (size * 2 - i == 111) tOutput (root);
	}
	return 0;
}