#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 y;
	int l, r;

	int val;

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

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

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

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

	int newnode (const int val)
	{
		v.push_back(node(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].val + sum(v[t].r);
		}
	}

	pair<int, int> split (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(v[t].l, k);
			v[t].l = r;                    
			recalc(t);
			return pair<int, int>(l, t);
		}
		else
		{
			auto [l, r] = split(v[t].r, k - cnt(v[t].l) - 1);
			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_at_pos (int &root, const int pos, const int val)
	{
		auto [l, r] = split(root, pos);
		const int m = newnode(val);
		root = merge(merge(l, m), r);	
	}

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

	void assign_at_pos (int &root, const int pos, const int val)
	{
		auto [l, temp] = split(root, pos);
		auto [m, r] = split(temp, 1);
		assert(cnt(m) == 1);
		v[m] = node(val);
		root = merge(merge(l, m), r);
	}

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

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

		return v[t].val;
	}

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

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

	vector<int> get_vals (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].val;
		else
			return get_kth(v[root].r, k - pivot - 1);
	}

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

	void print (int &root)
	{                               	
	}

	/// [kl, kr)
	pair<int, ll> mx_and_sum_by_index (int &root, const int kl, const int kr)
	{
		auto [l, temp] = split(root, kl);
		auto [m, r] = split(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;

	
}