#include <optional>
#include <format>

#pragma once

namespace cartesian_xless {

template<class Value>
struct Node;

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

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

	std::pair<Tree, Tree> split(size_t s);

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

	void insert(size_t i, const Value& v, auto& rng);

	Value erase(size_t i, auto& rng);

	size_t clear();

	Value at(size_t i, 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 Value>
struct Node {
	using TreeV = Tree<Value>;
	Value v;
	size_t size;
	TreeV l, r;

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

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

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

template<class Value>
auto Tree<Value>::split(size_t s)
		-> std::pair<Tree, Tree> {
	if (empty())
		return {};
	bool root_is_left = root->l.size() < s;
	if (root_is_left) {
		auto [rl, rr] = root->r.split(s - 1 - root->l.size());
		root->r = rl;
		recalculate_size();
		return { *this, rr };
	} else {
		auto [ll, lr] = root->l.split(s);
		root->l = lr;
		recalculate_size();
		return { ll, *this };
	}
}

template<class Value>
auto Tree<Value>::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 Value>
void Tree<Value>::insert(size_t i, const Value& v, auto& rng) {
	auto [l, r] = split(i);
	Tree middle{
		.root = new NodeV{
			.v = v,
			.size = 1,
			.l = {},
			.r = {},
		},
	};
	auto middle_r= merge(middle, r, rng);
	*this = merge(l, middle_r, rng);
}

template<class Value>
size_t Tree<Value>::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 Value>
Value Tree<Value>::erase(size_t i, auto& rng) {
	auto [l, r] = split(i);
	auto [rl, rr] = r.split(1);
	Value ans = rl.root->v;
	rl.clear();
	*this = merge(l, rr, rng);
	return ans;
}

template<class Value>
Value Tree<Value>::at(size_t i, auto& rng) {
	auto [l, r] = split(i);
	auto [rl, rr] = r.split(1);
	Value ans = rl.root->v;
	r = merge(rl, rr, rng);
	*this = merge(l, r, rng);
	return ans;
}

template<class Value>
std::string Tree<Value>::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 Value>
std::pair<std::string, std::vector<int>>
Tree<Value>::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 Value>
struct SmartArray {
	Tree<Value> tree;
	std::mt19937 rng{239};
	using uid = std::uniform_int_distribution<int>;

	void insert(size_t i, const Value& v) {
		tree.insert(i, v, rng);
	}

	Value erase(size_t i) {
		return tree.erase(i, rng);
	}

	Value at(size_t i) {
		return tree.at(i, rng);
	}

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

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