#include <bits/stdc++.h>

using namespace std;

struct treap_manager
{
private:
	struct node
	{
		/// левый и правый сыновья
		int l, r;
		/// ключ и приоритет
		int x, y;

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

		node(const int l_, const int r_, const int x_, const int y_) :
				l(l_), r(r_), x(x_), y(y_)
		{}
	};

	vector<node> pool;
	static mt19937 rng_priority;

	int add_node(const node &what)
	{
		const int num = int(pool.size());
		pool.push_back(what);
		return num;
	}

	/// разбить дерево на два : с ключами из [-inf, split_by) и [split_by, +inf)
	/// пользуемся только x-ами
	pair<int, int> split(const int root, const int split_by)
	{
		if (root == -1)
			return {-1, -1};

		/// если корень попал в левое поддерево
		if (pool[root].x < split_by)
		{
			const pair<int, int> right_split = split(pool[root].r, split_by);
			pool[root].r = right_split.first;
			return {root, right_split.second};
		}
			// если корень в правое поддерево
		else
		{
			const pair<int, int> left_split = split(pool[root].l, split_by);
			pool[root].l = left_split.second;
			return {left_split.first, root};
		}
	}


	/// даны два декартовых дерева, все ключи левого меньше всех ключей правого
	/// склеить их в одно (попортив их внутреннюю структуру)
	/// пользуемся только y-ами
	int merge(const int l, const int r)
	{
		if (l == -1)
			return r;
		if (r == -1)
			return l;

		/// перебираем, кто станет корнем
		if (pool[l].y > pool[r].y)
		{
			pool[l].r = merge(pool[l].r, r);
			return l;
		}
		else
		{
			pool[r].l = merge(l, pool[r].l);
			return r;
		}
	}

public:
	/// построить дерево по подотрезку массива [l, r)
	int build_subtree(vector<pair<int, int>> key_prior_pairs, const int l, const int r)
	{
		/// -1 -- условный номер пустой декартки
		if (l >= r)
			return -1;
		/// Если останется только одна вершина, то мы её найдём в качестве m
		/// и запустимся от пустых левых и правых поддеревьев.

		int m = -1;
		for (int i = l; i < r; i++)
			if (m == -1 || key_prior_pairs[m].second < key_prior_pairs[i].second)
				m = i;

		/// m -- вершина с наибольший y.
		const int left = build_subtree(key_prior_pairs, l, m);
		const int right = build_subtree(key_prior_pairs, m + 1, r);
		return add_node(node(left, right, key_prior_pairs[m].first, key_prior_pairs[m].second));
	}

	/// построить декартово дерево по набору пар (x, y)
	/// и вернуть индекс его корня в массиве pool
	int build_treap(vector<pair<int, int>> key_prior_pairs)
	{
		sort(key_prior_pairs.begin(), key_prior_pairs.end());
		return build_subtree(key_prior_pairs, 0, int(key_prior_pairs.size()));
	}

	bool has_key(int root, const int x)
	{
		while (root != -1)
		{
			if (pool[root].x == x)
				return true;
			if (pool[root].x < x)
				root = pool[root].r;
			else
				root = pool[root].l;
		}
		return false;
	}

	/// добавляет ключ x в дерево с индексом root и возвращает
	/// индекс получившегося дерева.
	int insert(const int root, const int x)
	{
		const int mid = add_node(node(x));
		int left, right;
		/// в left все ключи < x, в right все ключи >= x
		tie(left, right) = split(root, x);
		/// всё по порядку
		return merge(left, merge(mid, right));
	}

	/// удалить из дерева с индексом root ключ x и вернуть
	/// индекс получившегося дерева.
	/// если такого ключа нет, то не будем менять дерево,
	/// как минимум с точки зрения содержания.
	int erase(const int root, const int x)
	{
		int left, mid, right;
		tie(left, mid) = split(root, x);
		tie(mid, right) = split(mid, x + 1);
		/// теперь в left все ключи < x, в mid все ключи = x,
		/// а в right все ключи > x.
		return merge(left, right);
	}
};

int main()
{

	return 0;
}