// implicit treap: sum on subtree, same as size, glue segments in any order
#include <bits/stdc++.h>
using namespace std;

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

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

struct Node;
using PNode = Node *; // typedef Node * PNode;
struct Node
{
	int value;
	int size;
	long long total;
	PNode left;
	PNode right;

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

	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 recurOutput (PNode v)
{
	if (v == nullptr)
	{
		return;
	}
	cout << "(";
	recurOutput (v -> left);
	cout << v -> value;
//	cout << "|" << v -> size;
	recurOutput (v -> right);
	cout << ")";
}

void output (PNode v)
{
	recurOutput (v);
	cout << endl;
}

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

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

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

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

PNode tRemovePos (PNode v, int pos)
{
	auto one = tSplitK (v, pos);
	auto two = tSplitK (one.second, 1);
	// one.first | two.first | two.second
	// TODO: delete two.first
	tDelete (two.first);
	return tMerge (one.first, two.second);
}

int main ()
{
	int const size = 200000;
	PNode root = nullptr;
	for (int i = 1; i <= size; i++)
	{
		root = tInsertPos (root, i / 2, i);
//		output (root);
	}
	for (int i = 0; i <= size / 2; i++)
	{
		auto one = tSplitK (root, i);
		auto two = tSplitK (one.second, size / 2);
//		cout << two.first -> total << "  ";
//		recurOutput (one.first); cout << " ";
//		recurOutput (two.first); cout << " ";
//		recurOutput (two.second); cout << "\n";
		one.second = tMerge (two.second, two.first); // !!! order
		root = tMerge (one.first, one.second);
	}
	return 0;
}