// implicit treap: mass operations with relax, reverse on segment
#include <cassert>
#include <iostream>
#include <random>
#include <utility>
using namespace std;

//random_device dev;
//mt19937 gen (dev ());
mt19937 gen (1234567890);

int random (int range)
{
	return uniform_int_distribution <int> (0, range - 1) (gen);
}

struct Node;
using PNode = Node *;
struct Node
{
	int value;
	int size;
	long long total;
	bool rev;
	PNode left;
	PNode right;

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

	int leftSize ()
	{
		if (left == nullptr)
		{
			return 0;
		}
		return left -> size;
	}

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

	void recalc ()
	{
		size = 1;
		total = value;
		if (left != nullptr)
		{
			size += left -> size;
			total += left -> total;
		}
		if (right != nullptr)
		{
			size += right -> size;
			total += right -> total;
		}
	}
};

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

void tOutput (PNode t)
{
	tOutputRecur (t);
	cout << endl;
}

pair <PNode, PNode> tSplitK (PNode t, int k)
{ // first: k left; second: other
	if (t == nullptr)
	{
		return {nullptr, nullptr};
	}
	t -> relax ();
//	if (k - t -> leftSize () - 1 >= 0)
	if (t -> leftSize () < k)
	{
		auto temp = tSplitK (t -> right, k - t -> leftSize () - 1);
		t -> right = temp.first;
		t -> recalc ();
		return {t, temp.second};
	}
	else
	{
		auto temp = tSplitK (t -> left, k);
		t -> left = temp.second;
		t -> recalc ();
		return {temp.first, t};
	}
}

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

PNode tInsertPos (PNode t, int pos, int value)
{
	auto temp = tSplitK (t, pos);
	auto v = new Node (value);
	// (temp.first | v) | temp.second
	auto half = tMerge (temp.first, v);
	return tMerge (half, temp.second);
}

int main ()
{
	int const size = 10;
	PNode root = nullptr;
	tOutput (root);
	for (int i = 1; i <= size * 2; i += 2)
	{
		root = tInsertPos (root, i / 4, i);
//		tOutput (root);
	}
	for (int i = 0; i <= size / 2; i++)
	{
		auto one = tSplitK (root, i);
		auto two = tSplitK (one.second, size / 2);
		two.first -> rev ^= true;
//		tOutputRecur (one.first); cout << " ";
//		tOutputRecur (two.first); cout << " ";
//		tOutputRecur (two.second); cout << endl;
		cout << i << ": " << two.first -> total << endl;
		auto temp = tMerge (two.first, one.first);
		root = tMerge (temp, two.second);
//		tOutput (root);
	}
	tOutput (root);
	return 0;
}