// 5. Removed x. Added value. Split by left size. Reverse. Glue in other order.
#include <bits/stdc++.h>
using namespace std;

using Num = int;

#ifdef DEBUG
int const limit = 10;
#else
int const limit = 1000000;
#endif

mt19937 gen (1251521589);

struct Node;
typedef Node * PNode;
struct Node
{
	Num value;
	long long sum;
	int size;
	bool rev;
	PNode left;
	PNode right;

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

	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;
		if (left != nullptr) size += left -> size;
		if (right != nullptr) size += right -> size;
		sum = value;
		if (left != nullptr) sum += left -> sum;
		if (right != nullptr) sum += right -> sum;
	}
};

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

long long tSum (PNode t)
{
	return (t == nullptr) ? 0 : t -> sum;
}

pair <PNode, PNode> tSplitPos (PNode t, int pos)
{
	if (t == nullptr) return {nullptr, nullptr};
	t -> relax ();
	auto leftSize = tSize (t -> left);
	if (leftSize + 1 <= pos)
	{
		auto temp = tSplitPos (t -> right, pos - leftSize - 1);
		t -> right = temp.first;
		t -> recalc ();
		return {t, temp.second};
	}
	else
	{
		auto temp = tSplitPos (t -> left, pos);
		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 (uniform_int_distribution <int> (0, l -> size + r -> size - 1)
	    (gen) < l -> size)
	{
		l -> right = tMerge (l -> right, r);
		l -> recalc ();
		return l;
	}
	else
	{
		r -> left = tMerge (l, r -> left);
		r -> recalc ();
		return r;
	}
}

PNode tInsert (PNode t, Num value, int pos)
{
	auto temp = tSplitPos (t, pos);
	auto v = new Node (value);
	auto half = tMerge (temp.first, v);
	return tMerge (half, temp.second);
}

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

void tOutput (PNode t)
{
#ifdef DEBUG
	if (t != nullptr)
	{
		cout << t -> value << " ";
	}
	tOutputRecur (t);
	cout << endl;
#endif
}

tuple <int, long long, PNode> tCountBetween (PNode t, int lo, int hi)
{ // # [lo..hi)
	auto [a, b] = tSplitPos (t, lo); // a | b
	auto [c, d] = tSplitPos (b, hi - lo); // a | c | d
	auto res = tSize (c);
	auto res2 = tSum (c);
	b = tMerge (c, d);
	return {res, res2, tMerge (a, b)};
}

PNode tReverseBetween (PNode t, int lo, int hi)
{ // # [lo..hi)
	auto [a, b] = tSplitPos (t, lo); // a | b
	auto [c, d] = tSplitPos (b, hi - lo); // a | c | d
	if (c != nullptr)
	{
		c -> rev ^= true;
	}
	// d | c | a
/*
	b = tMerge (c, d);
	return tMerge (a, b);
*/
	auto e = tMerge (d, c);
	return tMerge (e, a);
}

int main ()
{
	PNode root = nullptr;
	cout << "limit = " << limit << endl;
	for (int i = 0; i < limit; i++)
	{
		root = tInsert (root, i, i / 2);
		tOutput (root);
	}
	for (int i = 0; i < limit / 2; i++)
	{
		auto [res, res2, t] = tCountBetween (root, i, i * 2);
		cout << "[" << i << ".." << i * 2 << ") " << res <<
		    " " << res2 << endl;
		root = t;
		tOutput (root);
	}
	for (int i = 0; i < limit / 2; i++)
	{
		root = tReverseBetween (root, i, i + limit / 2);
		tOutput (root);
	}
	return 0;
}