#include<iostream>
#include<random>


using namespace std;

mt19937 rng(time(0));

struct Node
{
	//int x;
	int data;
	int y;
    int tSize;
	bool rev;
	Node* left;
	Node* right;

	Node(int data_)
	{
		//x = x_;
		data = data_;
		y = rng();
		rev = 0;
		tSize = 1;
		left = nullptr;
		right = nullptr;
	}

};


int tRecalc(Node* t)
{
	if (t == nullptr)
		return 0;
	t->tSize = 1;
	if (t->left)
		t->tSize += t->left->tSize;
	if (t->right)
		t->tSize += t->right->tSize;
	return t->tSize;
}

void push(Node* t)//проталкивание переворачивания
{
	if (t == nullptr)
		return;
	if (!t->rev)
		return;

	auto temp = t->left;
	t->left = t->right;
	t->right = temp;

	t->rev = false;
	if (t->left != nullptr) t->left->rev ^= 1;
	if (t->right != nullptr) t->right->rev ^= 1;
}

int GetSize(Node* t)
{
	if (t == nullptr)
		return 0;
	return t->tSize;
}


pair<Node*, Node*> Split(Node* t, int i)
{
	if (t == nullptr)
		return { nullptr, nullptr };
	push(t);
	if (i < GetSize(t->left) + 1)
	{
		pair <Node*, Node*> leftres = Split(t->left, i);
		t->left = leftres.second;
		tRecalc(t);
		return { leftres.first, t };
	}
	else
	{
		pair <Node*, Node*> rightres = Split(t->right, i - GetSize(t->left) - 1);
		t->right = rightres.first;
		tRecalc(t);
		return { t, rightres.second };
	}
}

Node* Merge(Node* l, Node* r)
{
	if (l == nullptr)
		return r;
	if (r == nullptr)
		return l;

	if (l->y >= r->y)
	{
		push(l);
		l->right = Merge(l->right, r);
		tRecalc(l);
		return l;
	}
	else
	{
		push(r);
		r->left = Merge(l, r->left);
		tRecalc(r);
		return r;
	}
}



Node* Insert(Node* t, int i, int data)
{
	Node* newnode = new Node(data);
	//auto [L, R] = Split(t, data); 
	auto lr = Split(t, i);
	return Merge(Merge(lr.first, newnode), lr.second);
}


Node* Remove(Node* t, int i)
{
	auto lr = Split(t, i);
	auto temp = Split(lr.first, i - 1);
	//добавить освобождение памяти
	return Merge(temp.first, lr.second);
}


void SetToBeReversed(Node* t, int l, int r) //переворот подотрезка на индексах от l r
{
	auto temp = Split(t, r);
	auto temp2 = Split(temp.first, l - 1);
	if (temp2.second != nullptr)
		temp2.second->rev ^= 1;
	t = Merge(temp2.first, Merge(temp2.second, temp.second));
}



int main()
{

	return 0;
}