#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

mt19937 rng;
/// mt19937_64 rng ?
/// лучше rand

using ll = long long;

/// set -> map?
struct node
{
	/// long long y ?
	int x, y;
	int l, r;

	int val;

	int cnt;
	
	/// mx is maximum val in subtree
	/// sum is sum of x in subtree
	int mx;
	ll sum;

	node() : l(-1), r(-1) {}

	node (const int x_, const int val_) : 
		x(x_), y(rng()), l(-1), r(-1), val(val_), cnt(1), mx(val_), sum(x_) {}
};

const int inf = int(1e9) + 1;
               
struct treap_manager
{
	vector<node> v;

	int newnode (const int x, const int val)
	{
		v.push_back(node(x, val));
		return int(v.size()) - 1;
	}

	void recalc (const int t)
	{
		if (t != -1)
		{
			v[t].cnt = cnt(v[t].l) + 1 + cnt(v[t].r);
			v[t].mx = max({mx(v[t].l), v[t].val, mx(v[t].r)});
			v[t].sum = sum(v[t].l) + v[t].x + sum(v[t].r);
		}
	}

	pair<int, int> split_by_size (const int t, const int k) /// не const 
	{
		if (t == -1)
			return pair<int, int>(-1, -1);

		/// v[t].x >= x0
		if (cnt(v[t].l) >= k) 
		{
			auto [l, r] = split_by_size(v[t].l, k);
			v[t].l = r;                    
			recalc(t);
			return pair<int, int>(l, t);
		}
		else
		{
			auto [l, r] = split_by_size(v[t].r, k - cnt(v[t].l) - 1);
			v[t].r = l;
			recalc(t);
			return pair<int, int>(t, r);
		}
	}

	pair<int, int> split (const int t, const int x0) /// не const 
	{
		if (t == -1)
			return pair<int, int>(-1, -1);

		if (v[t].x >= x0) 
		{
			auto [l, r] = split(v[t].l, x0);
			///pair<int, int> p = split(v[t].l, x0);
			///int l = p.first, r = p.second;
			v[t].l = r;
			///v[t].cnt -= cnt(l);
			recalc(t);
			return pair<int, int>(l, t);
		}
		else
		{
			auto [l, r] = split(v[t].r, x0);
			v[t].r = l;
			recalc(t);
			return pair<int, int>(t, r);
		}
	}

	int merge (int l, int r) /// не const
	{
		if (l == -1)
			return r;
		if (r == -1)
			return l;

		if (v[l].y > v[r].y)
		{
			v[l].r = merge(v[l].r, r);
			recalc(l);
			return l;
		}
		else
		{
			v[r].l = merge(l, v[r].l);
			recalc(r);
			return r;
		}
	}

	void insert (int &root, const int x, const int val)
	{
		auto [l, r] = split(root, x);
		const int m = newnode(x, val);
		root = merge(merge(l, m), r);	
	}

	void remove (int &root, const int x)
	{
		auto [l, temp] = split(root, x);
		auto [m, r] = split(temp, x + 1);
		/// утечка памяти!
		root = merge(l, r);
	}

	int find (int &root, const int x)
	{
		auto [l, temp] = split(root, x);
		auto [m, r] = split(temp, x + 1);
		root = merge(merge(l, m), r);
		return m;
	}
	/// можно честный

	int find_min (int t)
	{
		if (t == -1)
			return inf;

		while (v[t].l != -1)
			t = v[t].l;

		return v[t].x;
	}

	int lower_bound (int &root, const int x)
	{
		auto [l, r] = split(root, x);
		const int ans = find_min(r);
		root = merge(l, r);
		return ans;
	}

	void dfs (const int root, vector<int> &ans)
	{
		if (root == -1)
			return;

		dfs(v[root].l, ans);
		ans.push_back(v[root].x);
		dfs(v[root].r, ans);
	}

	vector<int> get_keys (const int root)
	{
		vector<int> ans;
		dfs(root, ans);
		return ans;
	}

	int cnt (const int t)
	{
		return t == -1 ? 0 : v[t].cnt;
	}

	int mx (const int t)
	{
		return t == -1 ? -inf : v[t].mx;
	}

	ll sum (const int t)
	{
		return t == -1 ? 0LL : v[t].sum;	
	}

	int get_kth (const int root, const int k)
	{
		assert(0 <= k && k < cnt(root));

		const int pivot = cnt(v[root].l);
		if (k < pivot)
			return get_kth(v[root].l, k);
		else if (k == pivot)
			return v[root].x;
		else
			return get_kth(v[root].r, k - pivot - 1);
	}

	int get_kth_stupid (int &root, const int k)
	{
		auto [l, temp] = split_by_size(root, k);
		auto [m, r] = split_by_size(temp, 1);
		const int ans = v[m].x;
		root = merge(merge(l, m), r);
		return ans;
	}

	void print (int &root)
	{
		vector<int> keys = get_keys(root);
	
		for (const int x : keys)
			cout << x << " ";
		cout << endl;
		for (int i = 0; i < cnt(root); i++)
			cout << get_kth(root, i) << " ";
		cout << endl;
		for (int i = 0; i < cnt(root); i++)
			cout << get_kth_stupid(root, i) << " ";
		cout << endl;

		cout << "====" << endl;

		keys.push_back(inf);

		for (int l = 0; l < cnt(root); l++)
		for (int r = l + 1; r <= cnt(root); r++)
		{
			const auto ans1 = mx_and_sum_by_key(root, keys[l], keys[r]);
			const auto ans2 = mx_and_sum_by_index(root, l, r);
			assert(ans1 == ans2);
			cout << l << ' ' << r << ' ';
			cout << ans1.first << ' ' << ans1.second << endl;
		}
	}

	/// [xl, xr)
	pair<int, ll> mx_and_sum_by_key (int &root, const int xl, const int xr)
	{
		auto [l, temp] = split(root, xl);
		auto [m, r] = split(temp, xr);
		const pair<int, ll> ans(v[m].mx, v[m].sum);
		root = merge(merge(l, m), r);
		return ans;
	}

	/// [kl, kr)
	pair<int, ll> mx_and_sum_by_index (int &root, const int kl, const int kr)
	{
		auto [l, temp] = split_by_size(root, kl);
		auto [m, r] = split_by_size(temp, kr - kl);
		const pair<int, ll> ans(v[m].mx, v[m].sum);
		root = merge(merge(l, m), r);
		return ans;
	}
 
};

int main()
{
	treap_manager info;
	int root = -1;

	info.insert(root, 3, 11);
	info.print(root);
	info.insert(root, -1, 4);
	info.print(root);
	info.insert(root, 4, -2);
	info.print(root);
	info.insert(root, 2, 4);
	info.print(root);
	info.remove(root, 2);
	info.print(root);
	info.remove(root, 2);
	info.print(root);		
}