/// Implicit Randomized Treap (Cartesian Tree)
///   Simulate x (array index), simulate y (priority)
///   Store value
///   Maintain size of subtree
///   total: sum of values in subtree
///   largest: maximum of values in subtree
/// Base Functions
///   tSplitPos: split into first pos elements and the rest
///   tMerge: merge two trees
/// Array Interface
///   tInsertPos: insert value at position pos
///   tFindPos: return value at position pos
///   tAssignPos: assign value at position pos, assert it exists
///   tRemovePos: remove value at position pos
/// Debugging
///   tOutput: print bracket structure of tree
///   tOutput2: print vertical representation
/// Example Usage
///   Add 10^6 elements to the middle
///   Cut middle part, check total and largest
///   Reassign an element in the middle
///   Cut middle part, check total and largest again
///   Find values of all elements
///   Remove half of elements from positions 0, then 1, then 2, etc
///   (disabled) Remove other half of elements
#include <bits/stdc++.h>
using namespace std;

auto gen = mt19937 (time (0));
using uniform = uniform_int_distribution <int>;

struct Node;
using PNode = Node *;
using Num = long long;
int getSize (PNode t);
Num getTotal (PNode t);
Num getLargest (PNode t);
struct Node
{
	Num value;
	Num total;
	Num largest;
	int size;
	PNode left;
	PNode right;
	
	void recalc ()
	{
//		size = 1 + getSize (this -> left) + getSize (this -> right);
		size = 1 + getSize (left) + getSize (right);
		total = value + getTotal (left) + getTotal (right);
		largest = max (value,
		    max (getLargest (left), getLargest (right)));
	}
	
	Node (Num value_)
	{
		value = value_;
		total = value_;
		largest = value_;
		size = 1;
		left = nullptr;
		right = nullptr;
	}
	
	~Node ()
	{
		if (left != nullptr) delete left;
		if (right != nullptr) delete right;
	}
};

int getSize (PNode t) {return (t == nullptr) ? 0 : t -> size;}
Num getTotal (PNode t)
{return (t == nullptr) ? Num (0) : t -> total;}
Num getLargest (PNode t)
{return (t == nullptr) ? Num (LLONG_MIN) : t -> largest;}

pair <PNode, PNode> tSplitPos (PNode t, int pos)
{
	if (t == nullptr) return {nullptr, nullptr};
	auto leftSize = getSize (t -> left);
	if (pos <= leftSize)
	{
		auto p = tSplitPos (t -> left, pos);
		t -> left = p.second;
		t -> recalc ();
		return {p.first, t};
	}
	else
	{
		auto p = tSplitPos (t -> right, pos - leftSize - 1);
		t -> right = p.first;
		t -> recalc ();
		return {t, p.second};
	}
}

PNode tMerge (PNode l, PNode r)
{
	if (l == nullptr) return r;
	if (r == nullptr) return l;
	if (uniform (0, l -> size + r -> size - 1) (gen) >= 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 t, int pos, Num value)
{
	auto v = new Node (value);
	auto p = tSplitPos (t, pos);
	auto half = tMerge (p.first, v);
	return tMerge (half, p.second);
}

void tOutput (PNode t, bool doEndl = true)
{
	if (t != nullptr)
	{
		cout << '(';
		tOutput (t -> left, false);
//		cout << t -> value << '|' << t -> size;
		cout << t -> value;
		tOutput (t -> right, false);
		cout << ')';
	}
	if (doEndl) cout << '.' << endl;
}

void tOutput2 (PNode t, int depth = 1)
{
	if (t != nullptr)
	{
		tOutput2 (t -> left, depth + 1);
//		cout << setw (depth) << ' ' << t -> x << endl;
		cout << setw (depth * 4) << ' ' <<
		    "  value=" << t -> value <<
		    "  total=" << t -> total <<
		    "  largest=" << t -> largest <<
			endl;
		tOutput2 (t -> right, depth + 1);
	}
}

Num tFindPos (PNode t, int pos)
{
	if (t == nullptr) return Num (-1);
	auto leftSize = getSize (t -> left);
	if (leftSize == pos) return t -> value;
	if (leftSize > pos) return tFindPos (t -> left, pos);
	else return tFindPos (t -> right, pos - leftSize - 1);
}

PNode tAssignPos (PNode t, int pos, Num value)
{
	if (t == nullptr) assert (false);
	auto leftSize = getSize (t -> left);
	if (leftSize == pos)
	{
		t -> value = value;
		t -> recalc ();
		return t;
	}
	if (leftSize > pos)
	{
		t -> left = tAssignPos (t -> left, pos, value);
		t -> recalc ();
		return t;
	}
	else
	{
		t -> right = tAssignPos (t -> right,
		    pos - leftSize - 1, value);
		t -> recalc ();
		return t;
	}
}

PNode tRemovePos (PNode t, int pos)
{
	if (t == nullptr) return t;
	auto leftSize = getSize (t -> left);
	if (leftSize == pos)
	{
		auto res = tMerge (t -> left, t -> right);
		t -> left = nullptr;
		t -> right = nullptr;
		delete t;
		return res;
	}
	if (leftSize > pos)
	{
		t -> left = tRemovePos (t -> left, pos);
		t -> recalc ();
		return t;
	}
	else
	{
		t -> right = tRemovePos (t -> right, pos - leftSize - 1);
		t -> recalc ();
		return t;
	}
}

int main ()
{
/*
	Node u;
	u.x; u.y; u.left; u.right;
	PNode v;
	(*v).x; (*v).y;
	v -> x; v -> y;
*/
	int const n = int (1E6);
	PNode root = nullptr;
	
	for (int x = 0; x < n; x++)
	{
		root = tInsertPos (root, x / 2, Num (x));
		if (x < 0) {tOutput2 (root); cout << endl;}
		if (x < 10) tOutput (root);
	}
	
	{
		auto p = tSplitPos (root, 666666);
		auto q = tSplitPos (p.first, 333333);
		cout << q.second -> total << " " <<
		    q.second -> largest << endl;
		p.first = tMerge (q.first, q.second);
		root = tMerge (p.first, p.second);
	}
	
	{
		root = tAssignPos (root, 500000, 999998 + 2);
	}
	
	{
		auto p = tSplitPos (root, 666666);
		auto q = tSplitPos (p.first, 333333);
		cout << q.second -> total << " " <<
		    q.second -> largest << endl;
		p.first = tMerge (q.first, q.second);
		root = tMerge (p.first, p.second);
	}
	
	for (int x = 0; x < n; x++)
	{
		auto res = tFindPos (root, x);
		if (x < 10) {cout << x << ' ' << res << endl;}
	}
	
	for (int x = 0; x < n / 2; x++)
	{
		root = tRemovePos (root, x);
		if (getSize (root) <= 10) tOutput (root);
	}

	if (false) for (int x = 0; x < n / 2; x++)
	{
		root = tRemovePos (root, 0);
		if (getSize (root) <= 10) tOutput (root);
	}

	return 0;
}