#include <bits/stdc++.h>
using namespace std;

mt19937 rng_priority;

struct node
{
	int l, r;
	int x, y;

	int cnt;

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

struct treap_manager
{
	vector<node> pool;

	int add_node(const int x)
	{
		const int ans = int(pool.size());
		pool.push_back(node(x));
		return ans;
	}

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

	int merge(int l, int m, int r)
	{
		return merge(merge(l, m), r);
	}

	pair<int, int> split (const int t, const int xs)
	{
		if (t == -1)
			return pair<int, int>(-1, -1);

		int l, r;
		if (pool[t].x < xs)
		{
/// 		Так МОЖНО написать, но не нужно.
//			const int mem = pool[t].r;
//			pool[t].r = -1;
//			tie(l, r) = split(mem, x);
//          pool[t].r = l;

			tie(l, r) = split(pool[t].r, xs);
			pool[t].r = l;
			return pair<int, int>(t, r);
		}
		else
		{
//			pool[t].x >= x;

			tie(l, r) = split(pool[t].l, xs);
			pool[t].l = r;
			return pair<int, int>(l, t);
		}
	}

	int merge (int l, 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;
		}
	}

	/// добавить вершину ver в дерево tree
	int insert_node (const int tree, const int ver)
	{
		int l, r;
		tie(l, r) = split(tree, pool[ver].x);
		return merge(l, ver, r);
	}

	int insert_key (const int tree, const int x)
	{
		const int ver = add_node(x);
		return insert_node(tree, ver);
	}

	/// возвращает идентификатор дерева после удаления ключа x
	int remove_key (const int tree, const int x)
	{
		int l, m, r;
		tie(l, m) = split(tree, x);
		/// в l все ключи < x
		/// в m все ключи >= x
		tie(m, r) = split(m, x + 1);

		/// в m теперь ключ x
		return merge(l, r);
	}
};


void solve(istream &cin, ostream &cout)
{
}

int main()
{
	solve(cin, cout);
}