#include <optional>
#include <format>

#pragma once

namespace cartesian_yless {

template<class Key>
struct Node;

template<class Key>
struct Tree {
	using uid = std::uniform_int_distribution<size_t>;
	using NodeK = Node<Key>;
	NodeK* root = nullptr;

	bool empty() const {
		return root == nullptr;
	}

	std::pair<Tree, Tree> split(Key xs, bool strict);

	static Tree merge(Tree l, Tree r, auto& rng);

	bool insert(Key x, auto& rng);

	bool erase(Key x, auto& rng);

	size_t clear();

	bool find(Key x, auto& rng);

	std::string to_string() const;
	std::pair<std::string, std::vector<int>> to_leveled_string() const;

	size_t size() const;
	void recalculate_size();
};

template<class Key>
struct Node {
	using TreeK = Tree<Key>;
	Key x;
	size_t size;
	TreeK l, r;

	void recalculate_size() {
		size = 1 + l.size() + r.size();
	}
};

template<class Key>
size_t Tree<Key>::size() const {
	if (empty()) return 0;
	return root->size;
}

template<class Key>
void Tree<Key>::recalculate_size() {
	if (empty()) return;
	return root->recalculate_size();
}

template<class Key>
auto Tree<Key>::split(Key xs, bool strict)
		-> std::pair<Tree, Tree> {
	if (empty())
		return {};
	bool root_is_left = strict ? root->x < xs : root->x <= xs;
	if (root_is_left) {
		auto [rl, rr] = root->r.split(xs, strict);
		root->r = rl;
		recalculate_size();
		return { *this, rr };
	} else {
		auto [ll, lr] = root->l.split(xs, strict);
		root->l = lr;
		recalculate_size();
		return { ll, *this };
	}
}

template<class Key>
auto Tree<Key>::merge(Tree l, Tree r, auto& rng) -> Tree {
	if (l.empty())
		return r;
	if (r.empty())
		return l;
	bool root_is_left = uid(1, l.size() + r.size())(rng) <= l.size();
	if (root_is_left) {
		l.root->r = merge(l.root->r, r, rng);
		l.recalculate_size();
		return l;
	} else {
		r.root->l = merge(l, r.root->l, rng);
		r.recalculate_size();
		return r;
	}
}

template<class Key>
bool Tree<Key>::insert(Key x, auto& rng) {
	auto [l, r] = split(x, true);
	auto [rl, rr] = r.split(x, false);
	bool inserted = rl.empty();
	if (inserted)
		rl.root = new NodeK{
			.x = x,
			.size = 1,
			.l = {},
			.r = {},
		};
	r = merge(rl, rr, rng);
	*this = merge(l, r, rng);
	return inserted;
}

template<class Key>
size_t Tree<Key>::clear() {
	if (empty())
		return 0;
	size_t ans = 0;
	ans += root->l.clear();
	ans += root->r.clear();
	delete root; ++ans;
	root = nullptr;
	return ans;
}

template<class Key>
bool Tree<Key>::erase(Key x, auto& rng) {
	auto [l, r] = split(x, true);
	auto [rl, rr] = r.split(x, false);
	bool ans = !rl.empty();
	rl.clear();
	*this = merge(l, rr, rng);
	return ans;
}

template<class Key>
bool Tree<Key>::find(Key x, auto& rng) {
	auto [l, r] = split(x, true);
	auto [rl, rr] = r.split(x, false);
	bool ans = !rl.empty();
	r = merge(rl, rr, rng);
	*this = merge(l, r, rng);
	return ans;
}

template<class Key>
std::string Tree<Key>::to_string() const {
	if (empty())
		return "[]";
	std::string ans = "[";
	ans += root->l.to_string();
	ans += std::format("{{{} {}}}", root->x, root->y);
	ans += root->r.to_string();
	ans += ']';
	return ans;
}

template<class Key>
std::pair<std::string, std::vector<int>>
Tree<Key>::to_leveled_string() const {
	if (empty())
		return { "[]", {0, 0} };
	std::string ans = "[";
	std::vector<int> lvl = { 0 };
	auto [lans, llvl] = root->l.to_leveled_string();
	ans += lans;
	for (int i : llvl)
		lvl.push_back(1 + i);
	std::string root_str = std::format("{{{} {}}}", root->x, root->y);
	ans += root_str;
	for (char c : root_str)
		lvl.push_back(0);
	auto [rans, rlvl] = root->r.to_leveled_string();
	ans += rans;
	for (int i : rlvl)
		lvl.push_back(1 + i);
	ans += ']';
	lvl.push_back(0);
	return { ans, lvl };
}

template<class Key>
struct Set {
	Tree<Key> tree;
	std::mt19937 rng{239};
	using uid = std::uniform_int_distribution<int>;

	void insert(Key x) {
		tree.insert(x, rng);
	}

	bool erase(Key x) {
		return tree.erase(x, rng);
	}

	bool contains(Key x) {
		return tree.find(x, rng);
	}

	size_t size() const {
		return tree.size();
	}

	~Set() {
		tree.clear();
	}
};
}