// Cartesian tree: tSplit+tMerge, tInsert+tRemove, debug output
// reverse sub-array in O (log size)
#include <bits/stdc++.h>
using namespace std;

using Num = int;

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;
	bool rev;

	Node (Num value_)
	{
		value = value_;
		size = 1;
		left = nullptr;
		right = nullptr;
		rev = false;
	}

	void relax ()
	{
		if (rev)
		{
			swap (left, right);
			rev = false;
			if (left != nullptr) left -> rev ^= true;
			if (right != nullptr) right -> rev ^= true;
		}
	}

	void recalc ()
	{
		assert (this != nullptr);
		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};
	t -> relax ();
	auto leftSize = tSize (t -> left);
	if (leftSize >= k) // k <= leftSize
	{
		auto temp = tSplitSize (t -> left, k);
		t -> left = temp.second;
		t -> recalc ();
		return {temp.first, t};
	}
	else // k > leftSize    <=>    k >= leftSize + 1
	{
		auto temp = tSplitSize (t -> right, k - leftSize - 1);
		t -> right = temp.first;
		t -> recalc ();
		return {t, temp.second};
	}
}

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

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;
	t -> relax ();
//	cout << "(";
	tOutput (t -> left);
	cout << t -> value;
//	cout << t -> value << "|" << t -> size;
	tOutput (t -> right);
//	cout << ")";
}

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

PNode tReverseSegment (PNode t, int start, int len)
{ // [0..start) rev[start..start + len) [len..end)
  // one.first    two.first          two.second
	auto one = tSplitSize (t, start);
	auto two = tSplitSize (one.second, len);
	two.first -> rev ^= true;
	auto half = tMerge (two.first, two.second);
	return tMerge (one.first, half);
}

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