pair<NH, NH> split(NH t, int k)
{
	if (!t)
	{
		return { nullptr, nullptr };
	}
	if (k > t->x)
	{
		auto p = split(t->right, k);
		t->right = p.first;
		return { t, p.second };
	}
	else
	{
		auto p = split(t->left, k);
		t->left = p.second;
		return { p.first, t };
	}
}

NH merge(NH t1, NH t2)
{
	if (!t2)
	{
		return t1;
	}
	if (!t1)
	{
		return t2;
	}
	if (t1->y > t2->y)
	{
		t1->right = merge(t1->right, t2);
		return t1;
	}
	else
	{
		t2->left = merge(t1, t2->left);
		return t2;
	}
}

NH erase(NH t, int k)
{
	if (!contains(t, k))
	{
		return t;
	}
	auto p = split(t, k);
	auto pp = split(p.first, k - 1);
	return merge(pp.first, p.second);
}