#include <bits/stdc++.h>

using namespace std;

mt19937 rng_priority;

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

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

		/// Из-за особенностей реализации изначально задаю параметры
		/// вершины, как будто у неё нет детей, а потом вызываю
		/// recalc. Чуть изменив сигнатуру recalc, его можно
		/// сделать методом для node, после чего вызвать его из
		/// конструктора. Как конкретно это реализовать -- вопрос
		/// вкуса. В этой реализации получается, что <<настоящим>>
		/// классом с настоящим интерфейсом является только treap_manager,
		/// а node -- просто структура с полями. В принципе, можно было
		/// даже заменить массив pool на кучу массивов для отдельных
		/// параметров вершин, но с такой реализацией просто менее приятно
		/// работать.
		node(const int l_, const int r_, const int x_, const int y_) :
				l(l_), r(r_), x(x_), y(y_), cnt(1)
		{}
	};

	vector<node> pool;

	int get_cnt(const int ver) const
	{
		return ver == -1 ? 0 : pool[ver].cnt;
	}

	void recalc(const int ver)
	{
		if (ver != -1)
			pool[ver].cnt = get_cnt(pool[ver].l) + 1 + get_cnt(pool[ver].r);
	}

	/// Добавляет вершину в массив pool и возвращает её индекс. Важно: это единственный способ <<неэфемерно>> создать
	/// вершину, то есть добавить её в pool. Можно было бы
	/// в каждом месте, где нужно
	int add_node(const node &what)
	{
		const int num = int(pool.size());
		pool.push_back(what);
		/// Важно, нужно здесь вызвать recalc от вершины.
		recalc(num);
		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;
			recalc(root);
			return {root, right_split.second};
		}
			/// если корень в правое поддерево
		else
		{
			const pair<int, int> left_split = split(pool[root].l, split_by);
			pool[root].l = left_split.second;
			recalc(root);
			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);
			recalc(l);
			return l;
		}
		else
		{
			pool[r].l = merge(l, pool[r].l);
			recalc(r);
			return r;
		}
	}

public:
	/// Построить дерево по подотрезку массива [l, r).
	int build_subtree(const 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;
	}

	/// Найти k-тый элемент в дереве с корнем root, 0-индексация.
	int get_kth_element(int root, int k) const
	{
		/// -1 -- условное значение, которые возвращается, когда k-того элемента в поддереве нет.
		if (k < 0 || k >= get_cnt(root))
			return -1;

		while (root != -1)
		{
			/// Пошли в левое поддерево, так как искомый элемент там.
			if (get_cnt(pool[root].l) > k)
				root = pool[root].l;
				/// Искомый элемент находится в корне.
			else if (get_cnt(pool[root].l) == k)
				return pool[root].x;
			else
			{
				/// Вычли левое поддерево и корень, после чего пошли в правое.
				k -= get_cnt(pool[root].l) + 1;
				root = pool[root].r;
			}
		}

		assert(false);
		return -1;
	}

	/// Сколько в дереве ключей < x? Считаем, что все ключи различны
	int order_of_key(int root, const int x)
	{
		int ans = 0;
		while (root != -1)
		{
			if (pool[root].x < x)
				ans++;
			if (pool[root].x <= x)
			{
				ans += get_cnt(pool[root].l);
				root = pool[root].r;
			}
			else
				root = pool[root].l;
		}
		return ans;
	}

	/// Добавляет ключ x в дерево с индексом root и возвращает индекс получившегося дерева.
	/// Если ключ уже был, то добавляется ещё один. Идеально работает даже если root == -1!
	void insert(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);
		/// Склеиваем всё в правильном поррядке.
		root = merge(left, merge(mid, right));
	}

	/// Удалить из дерева с индексом root все ключи x и вернуть индекс получившегося дерева.
	/// Если ключей x нет, то не будем менять дерево, как минимум с точки зрения содержания.
	void erase(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.
		root = merge(left, right);
	}
};

int main()
{

}