#include<iostream>
#include<random>


using namespace std;

mt19937 rng(time(0));

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

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


pair<Node*, Node*> Split(Node* t, int x)
{
	if (t == nullptr)
		return { nullptr, nullptr };

	if (x < t->x)
	{
		pair <Node*, Node*> leftres = Split(t->left, x);
		t->left = leftres.second;
		return { leftres.first, t };
	}
	else
	{
		pair <Node*, Node*> rightres = Split(t->left, x);
		t->right = rightres.first;
		return {t, rightres.second};
	}
}

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

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



Node* Insert(Node* t, int x)
{
	Node* newnode = new Node(x);
	//auto [L, R] = Split(t, x);
	auto lr = Split(t, x);
	return Merge(Merge(lr.first, newnode), lr.second);
}


Node* Remove(Node* t, int x)
{
	auto lr = Split(t, x);
	auto temp = Split(lr.first, x-1);
	//добавить освобождение памяти
	return Merge(temp.first, lr.second);
}



int main()
{
	return 0;
}