#include <bits/stdc++.h>

using namespace std;

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

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

	vector<node> pool;
	mt19937 rng_priority;

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

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

int main()
{

	return 0;
}