#include <bits/stdc++.h>

using namespace std;

mt19937 rng_priority;

/// То, что мы изучали на паре -- это декартово дерево по явному ключу, то есть просто разновидность
/// двоичного дерева поиска. Но декартово дерево (как и многие другие деревья поиска) можно модифицировать,
/// чтобы сделать его НЕЯВНЫМ. Несмотря на название, неявное декартово дерево (implicit treap) -- не
/// дерево поиска в привычном смысле. Правильнее сказать, что это "массив на стероидах". А именно,
/// одни из базовых вещей, которые оно умеет: найти элемент на k-той позиции массива, вставить ещё один
/// элемент между k-тым и (k+1)-ым элементами массива (и перенумеровать элементы итогового массива),
/// удалить элемента на k-той позиции, вырезать (sic!) произвольный кусок массива и сделать его
/// новым массивом, подклеить один массив к концу другого... И всё это за O(log n)! Более того,
/// интерфейс неявной декартки можно расширить, чтобы поддерживать операции, реализуемые деревом отрезков:
/// максимум на подотрезке, сумма на подотрезке и так далее. Более того, несмотря на то, что мы не обсуждали
/// так называемые "массовые изменения" в деревьях отрезков, неявное декартово дерево тоже их поддерживает.
/// Просто чудо, а не структура, верно?
struct implicit_treap_manager
{
private:
	/// Теперь подробнее о том, что происходит. Раньше у нас были настоящие ключи, по которым у нас было настоящее
	/// дерево поиска. Но ещё мы умели по ключу получать его порядковый номер внутри дерева. Это делалось с помощью
	/// количеств вершин в поддеревьях. Представим себе, что мы заменили каждый ключ на его порядковый номер.
	/// Это немного странная операция (мы забыли как раз именно ту информацию, которую нам нужно было хранить), но
	/// смысл как раз в том, что явная и неявная декартки -- не взаимозаменяемые структуры данных, они решают разные
	/// задачи. После такой замены условие двоичного дерева поиска всё ещё выполняется, но теперь ключи можно не
	/// хранить, а считать через количества вершин в поддеревьях! Собственно, поэтому такие ключи называются неяными,
	/// а вся структура данных -- декартово дерево по неявному ключу. Что произошло? Теперь нам не нужно поддерживать
	/// условие того, что все ключи в левом поддереве меньше ключа в корне, а все ключи в правом поддереве -- больше.
	/// Такое условие всегда выполняется автоматически просто по определению неявных ключей. Но мы всё ещё можем
	/// хранить в каждой вершине какую-то информацию (это уже не ключ, то есть никаких ограничений на эту инфомрацию
	/// не накладывается), находить вершину с неявным ключом k, делать merge деревьев (при этом "притворяемся", что в
	/// правом из склеиваемых деревьев все ключи больше: так как мы ключе больше явно не храним, то при такой склейке
	/// ничего не сломается). Если подумать, то неявное декартово дерево действительно ведёт себя как обешанный
	/// "массив на стероидах".

	/// Повторюсь -- неявный ключ вершины это количество вершин, в которых был бы меньший ключ, чем в ней, ЕСЛИ БЫ
	/// наше дерево было настоящим деревом поиска.
	struct node
	{
		/// Левый и правый сыновья:
		int l, r;
		/// Приоритет (ключ пропал):
		int y;
		/// Количество вершин в поддереве, в явной декартке оно было полезно, а в неявной всегда нужно:
		int cnt;
		/// Внутренняя информация: число в вершине и максимум в поддереве (числа в вершинах не обязаны идти в
		/// каком-либо порядке, они не ключи, наш массив может быть произвольным):
		int ver_num, subtree_max;

		node(const int number) : l(-1), r(-1), y(rng_priority()), cnt(1),
		                         ver_num(number), subtree_max(number)
		{}

		/// Из-за особенностей реализации изначально задаю параметры вершины, как будто у неё нет детей, а потом
		/// вызываю recalc. Чуть изменив сигнатуру recalc, его можно сделать методом для node, после чего вызвать
		/// его из конструктора. Как конкретно это реализовать -- вопрос вкуса. В этой реализации получается, что
		/// "настоящим" классом с настоящим интерфейсом является только implicit_treap_manager, а node -- просто
		/// структура с полями. В принципе, можно было даже заменить массив pool на кучу массивов для отдельных
		/// параметров вершин, но с такой реализацией просто менее приятно работать.
		node(const int l_, const int r_, const int number, const int y_) :
				l(l_), r(r_), y(y_), cnt(1), ver_num(number), subtree_max(number)
		{}
	};

	vector<node> pool;

	/// Количество вершин в поддереве (0, если поддерево пустое).
	int get_cnt(const int ver) const
	{
		return ver == -1 ? 0 : pool[ver].cnt;
	}

	/// Наибольшее число в поддереве (-inf, если поддерево пустое).
	int get_max(const int ver) const
	{
		return ver == -1 ? numeric_limits<int>::min() : pool[ver].subtree_max;
	}

	/// Максимум пересчитывается также, как и количество вершин в поддереве.
	void recalc(const int ver)
	{
		if (ver != -1)
		{
			pool[ver].cnt = get_cnt(pool[ver].l) + 1 + get_cnt(pool[ver].r);
			pool[ver].subtree_max = max(pool[ver].ver_num,
			                            max(get_max(pool[ver].l), get_max(pool[ver].r)));
		}
	}

	/// Добавляет вершину в массив pool и возвращает её индекс. Важно: это единственный способ "неэфемерно" создать
	/// вершину, то есть добавить её в pool. Можно было бы в каждом месте, где нужно добавить вершину в pool делать
	/// recalc, но это была бы ненужная дубликация кода.
	int add_node(const node &what)
	{
		const int num = int(pool.size());
		pool.push_back(what);
		/// Важно, нужно здесь вызвать recalc от вершины.
		recalc(num);
		return num;
	}

	/// Разбить массив на два: первые split_by его элементов и последние get_cnt(root) - split_by его элементов.
	/// Структура исходного массива при этом портится, конечно же. Раньше здесь мы пользовались ключами, но теперь
	/// у нас нет ключей (ещё можно сказать, что ключи есть, но они однозначно выражаются через размеры поддеревьев)
	/// и поэтому мы пользуемся cnt-шками. Всё на удивление хорошо работает.
	pair<int, int> split(const int root, const int split_by)
	{
		if (root == -1)
			return {-1, -1};

		/// Разбираем случай, когда корень попадёт в левую часть ответа. Раньше мы проверяли pool[root].x < split_by,
		/// теперь (неявный) ключ корня -- количество вершин в левом поддереве, так что мы проверяем такое условие:
		if (get_cnt(pool[root].l) < split_by)
		{
			/// Здесь небольшая тонкость: мы уже отнесли 1 + get_cnt(pool[root].l) элементов в левую часть ответа:
			/// корень и всё его правое поддерево, поэтому из split_by нужно вычесть это количество.
			const pair<int, int> right_split = split(pool[root].r, split_by - 1 - get_cnt(pool[root].l));
			pool[root].r = right_split.first;
			recalc(root);
			return {root, right_split.second};
		}
		else
		{
			/// А в этом случае ничего вычитать не надо, так как, если split_by <= get_cnt(pool[root].l), то первые
			/// split_by элементов левого поддерева -- в точности первые split_by элементов всего.
			const pair<int, int> left_split = split(pool[root].l, split_by);
			pool[root].l = left_split.second;
			recalc(root);
			return {left_split.first, root};
		}
	}

	/// Склеить массивы l и r в таком порядке, попортив при этом их внутреннюю структуру, и вернуть результат.
	/// Поскольку ключи теперь существуют только в нашем воображении, условие о том, что ключи в l меньше
	/// ключей в r теперь не только не нужно, а даже не может быть сформулировано так, чтобы оно имело смысл.
	/// По сравнению со случаем явной декартки, реализация ВООБЩЕ не изменилась, так как операция merge
	/// использовала только приоритеты и не интересовалась ключами вообще.
	int merge(const int l, const int r)
	{
		if (l == -1)
			return r;
		if (r == -1)
			return l;

		/// Перебираем, кто станет корнем.
		if (pool[l].y > pool[r].y)
		{
			pool[l].r = merge(pool[l].r, r);
			/// Поменяли у вершины левого или правого ребёнка -- делаем recalc!
			recalc(l);
			return l;
		}
		else
		{
			pool[r].l = merge(l, pool[r].l);
			/// Поменяли у вершины левого или правого ребёнка -- делаем recalc!
			recalc(r);
			return r;
		}
	}

public:
	/// Построить дерево по подотрезку массива [l, r).
	int build_subtree(const vector<int> &numbers, const vector<int> &priors, const int l, const int r)
	{
		/// -1 -- условный номер пустой декартки.
		if (l >= r)
			return -1;
		/// Если останется только одна вершина, то мы её найдём в качестве m и запустимся от пустых
		/// левых и правых поддеревьев.
		const int m = max_element(priors.begin() + l, priors.end() + r) - priors.begin();
		/// m -- вершина с наибольшим приоритетом на подотрезке.
		const int left = build_subtree(numbers, priors, l, m);
		const int right = build_subtree(numbers, priors, m + 1, r);
		return add_node(node(left, right, numbers[m], priors[m]));
	}

	/// Преобразовать настоящий массив в неявное декартово дерево.
	int build_treap(const vector<int> &numbers)
	{
		/// Ничего не сортируем, так как numbers -- не ключи! Это внутренние данные, ключи у нас неявные
		/// и отсортированы автоматически. Ну а приоритеты мы сами выбираем.
		vector<int> priors(numbers.size());
		for (auto &it : priors)
			it = rng_priority();
		return build_subtree(numbers, priors, 0, int(numbers.size()));
	}

	/// Добавить число number в конец массива.
	void push_back(int &root, const int number)
	{
		const int right = add_node(node(number));
		root = merge(root, right);
	}

	/// Сдвинуть массив по циклу: склеить последние get_cnt(root) - shift и первые shift элементов, в таком порядке.
	void shift_cyclically(int &root, const int shift)
	{
		int left, right;
		/// left -- первые shift элементов, right -- последние get_cnt(root) - shift.
		tie(left, right) = split(root, shift);
		/// Склеиваем куски обратно, но меняем left и right местами, поскольку хотим циклический сдвиг.
		root = merge(right, left);
	}

	/// Максимум на подотрезке [l, r) массива.
	int segment_max(int &root, const int l, const int r)
	{
		int left, mid, right;
		/// left -- первые l элементов, mid -- средние r - l, right -- последние get_cnt(root) - r.
		tie(left, mid) = split(root, l);
		tie(mid, right) = split(mid, r - l);
		const int ans = get_max(mid);
		/// Склеиваем куски обратно, в том же порядке.
		root = merge(merge(left, mid), right);
		return ans;
	}

	/// Найти k-тый элемент массива.
	int get_kth_element(int root, int k) const
	{
		/// -1 -- условное значение, которые возвращается, когда k-того элемента в массиве нет.
		if (k < 0 || k >= get_cnt(root))
			return -1;

		while (root != -1)
		{
			/// Пошли в левое поддерево, так как искомый элемент там.
			if (get_cnt(pool[root].l) > k)
				root = pool[root].l;
				/// Искомый элемент находится в корне.
			else if (get_cnt(pool[root].l) == k)
				return pool[root].ver_num;
			else
			{
				/// Вычли левое поддерево и корень, после чего пошли в правое.
				k -= get_cnt(pool[root].l) + 1;
				root = pool[root].r;
			}
		}
	}

	/// Удалить элемент на позиции k.
	void erase(int &root, const int k)
	{
		/// Удаляемый элемент должен быть в массиве.
		assert(0 <= k && k < get_cnt(root));

		int left, mid, right;
		tie(left, mid) = split(root, k);
		tie(mid, right) = split(root, 1);
		/// mid -- как раз только удалённый элемент, так что его склеивать не нужно.
		root = merge(left, right);
	}

	/// Вставить число number после первых k элементов.
	void insert(int &root, const int k, const int number)
	{
		/// 0 -- до всего, get_cnt(root) -- после всего.
		assert(0 <= k && k <= get_cnt(root));

		int left, right;
		tie(left, right) = split(root, k);
		/// Добавили вершину.
		const int mid = add_node(number);
		root = merge(merge(left, mid), right);
	}
};

int main()
{
}