// Cartesian tree: tSplit+tMerge, tInsert+tRemove, debug output
// persistent tree
#include <bits/stdc++.h>
using namespace std;

using Num = long long;

mt19937 rndBits (123456);
#ifdef DEBUG
uniform_int_distribution <int> gen (0, 100);
#else
uniform_int_distribution <int> gen (0, 1000000000);
#endif

struct Node;
typedef Node * PNode;
struct Node
{
	Num value;
	int size;
	PNode left;
	PNode right;

	Node (Num value_, PNode left_ = nullptr, PNode right_ = nullptr)
	{
		value = value_;
		left = left_;
		right = right_;
		size = 1;
		if (left != nullptr) size += left -> size;
		if (right != nullptr) size += right -> size;
	}
};

int tSize (PNode const t)
{
	return (t == nullptr) ? 0 : t -> size;
}

pair <PNode, PNode> tSplitSize (PNode t, int k)
{ // res.first: first k elements;   res.second: all other elements
	if (t == nullptr) return {nullptr, nullptr};
	auto leftSize = tSize (t -> left);
	if (leftSize >= k) // k <= leftSize
	{
		auto temp = tSplitSize (t -> left, k);
		auto newT = new Node (t -> value, temp.second, t -> right);
//		t -> left = temp.second;
//		t -> recalc ();
		return {temp.first, newT};
	}
	else // k > leftSize    <=>    k >= leftSize + 1
	{
		auto temp = tSplitSize (t -> right, k - leftSize - 1);
		auto newT = new Node (t -> value, t -> left, temp.first);
//		t -> right = temp.first;
//		t -> recalc ();
		return {newT, temp.second};
	}
}

PNode tMerge (PNode l, PNode r)
{
	if (l == nullptr) return r;
	if (r == nullptr) return l;
	if (uniform_int_distribution <int> (0, l -> size + r -> size)
	    (rndBits) < l -> size)
	{
//		l -> right = tMerge (l -> right, r);
//		l -> recalc ();
		return new Node (l -> value, l -> left, tMerge (l -> right, r));
	}
	else
	{
//		r -> left = tMerge (l, r -> left);
//		r -> recalc ();
		return new Node (r -> value, tMerge (l, r -> left), r -> right);
	}
}

PNode tInsertAt (PNode t, Num value, int pos)
{ // 0[...)len  ->  0[...)pos, value, pos[...)len
	auto temp = tSplitSize (t, pos);
	auto v = new Node (value);
	auto half = tMerge (temp.first, v);
	return tMerge (half, temp.second);
}

void recurDelete (PNode t)
{
	if (t == nullptr) return;
	recurDelete (t -> left);
	recurDelete (t -> right);
	delete t;
}

PNode tRemoveAt (PNode t, int pos)
{ // 0[...)len  ->  0[...)pos, pos+1[...)len
	auto one = tSplitSize (t, pos); // 0[...)pos, pos[...)len
	auto two = tSplitSize (one.second, 1); // pos[...)pos+1,  pos+1[...)len
	recurDelete (two.first); // can omit this
	return tMerge (one.first, two.second);
}

Num tElementAt (PNode const t, int pos)
{
	if (t == nullptr) assert (false);
	auto leftSize = tSize (t -> left);
	if (pos == leftSize) return t -> value;
	if (pos < leftSize) return tElementAt (t -> left, pos);
	return tElementAt (t -> right, pos - leftSize - 1);
}

void tOutput (PNode t)
{
	if (t == nullptr) return;
//	cout << "(";
	tOutput (t -> left);
	cout << t -> value << " ";
	tOutput (t -> right);
//	cout << ")";
}

void tOutputAll (PNode t)
{
#ifdef DEBUG
	tOutput (t);
	cout << endl;
#else
	assert (t == NULL || t != NULL);
#endif
}

int main ()
{
	PNode root = nullptr;
	int const limit = 10;
	for (int i = 0; i < limit; i++)
	{
		root = tInsertAt (root, i, i);
		tOutputAll (root);
	}
	return 0;
}