#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 деревьев (при этом "притворяемся", что в
	/// правом из склеиваемых деревьев все ключи больше: так как мы ключе больше явно не храним, то при такой склейке
	/// ничего не сломается). Если подумать, то неявное декартово дерево действительно ведёт себя как обешанный
	/// "массив на стероидах".

	/// Повторюсь -- неявный ключ вершины это количество вершин, в которых был бы меньший ключ, чем в ней, ЕСЛИ БЫ
	/// наше дерево было настоящим деревом поиска.

	/// По сравнению с предыдущим кодом, я сделал два изменения: существенное (добавлена возможность разворвачивать
	/// подотрезки массива) и несущественное (убрал приоритеты и сделал merge с помощью случайных чисел). Остальное
	/// почти не поменялось.
	struct node
	{
		/// Левый и правый сыновья:
		int l, r;

		/// A и Б сидели на трубе...
		/// Здесь раньше были ключ и приоритет, но теперь их нет.

		/// Количество вершин в поддереве, в явной декартке оно было полезно, а в неявной всегда нужно:
		int cnt;
		/// Внутренняя информация: число в вершине и максимум в поддереве (числа в вершинах не обязаны идти в
		/// каком-либо порядке, они не ключи, наш массив может быть произвольным):
		int ver_num, subtree_max;

		/// Мы ОБЕЩАЕМ развернуть поддерево вершины в будущем. То есть если вершина соответствует подотрезку
		/// [l, r) массива, то мы обещаем развернуть этот подотрезок. Смысл этой операции в том, что мы не можем
		/// каждый раз, когда нас просят развернуть отрезок, на самом деле его разворачивать за O(r - l). Но мы
		/// можем заметить, что это и не нужно. На самом деле нужно разворачивать поддерево вершины только когда
		/// уже совсем прижало и без этого всё поломается.
		bool to_reverse;

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

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

	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)));
		}
	}

	/// Обещаем, что развернём поддерево вершины.
	void promise_reverse (const int ver)
	{
		if (ver != -1)
			/// Развернуть что-то два раза -- то же самое, что и не разворачивать вообще.
			pool[ver].to_reverse ^= true;
	}

	/// Совсем прижало, если не развернуть поддерево вершины ver сейчас, то всё сломается.
	void push (const int ver)
	{
		/// Если поддерево пусто или его не надо разворачивать, но ничего не делаем.
		if (ver != -1 && pool[ver].to_reverse)
		{
			pool[ver].to_reverse = true;
			/// Чтобы развернуть массив, достаточно поменять местами его соответствующие префикс и суффикс,
			/// а потом уже развернуть этот префикс и суффикс. Это можно записать так: (uv)^R = v^R u^R.
			swap(pool[ver].l, pool[ver].r);
			/// Поменяли детей местами, теперь про них обещаем, что их развернём. По-настоящему их развернём
			/// тоже только когда прижмёт.
			promise_reverse(pool[ver].l);
			promise_reverse(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). Давайте оценим вероятность того, что такой if выполнится. Так
		/// как мы выбираем приоритеты случайным образом, то эта вероятность равна тому, что из get_cnt(l) + get_cnt(r)
		/// случайных приоритетов большим оказался один из get_cnt(l), то есть get_cnt(l) / (get_cnt(l) + get_cnt(r)).
		/// Давайте заменим этот if просто на событие, которое выполняется ровно с такой вероятностью. Разумеется,
		/// это НЕ равносильно использованию приоритетов: хотя вероятность каждой конкретной склейки мы просимулировали
		/// правильно, события такого рода НЕ независимы, если мы используем приоритеты (но независимы, если мы каждый
		/// раз клеим случайно). То, что случайные склейка всё ещё работает НУЖНО доказывать. Это НЕ очевидно, но
		/// это верно. В любом случае, пока мы не дошли до персистентности, использовать случайную склейку не
		/// обязательно и можно продолжать использовать приоритеты. Более того, использовать приоритеты чуть быстрее,
		/// так как не нужно много раз вызывать относительно медленную операцию порождения псевдослучайных чисел.
		uniform_int_distribution<int> distr(0, get_cnt(l) + get_cnt(r) - 1);
		/// Если случайное число из отрезка [0, get_cnt(l) + get_cnt(r)) оказалось меньше get_cnt(l), то сделаем
		/// l корнем склеенного дерева. То есть вероятность этого get_cnt(l) / (get_cnt(l) + get_cnt(r)).
		if (distr(rng_priority) < get_cnt(l))
		{
			/// Прижало: мы хотим поменять ребёнка у l. Если мы не развернём вершину сейчас, то всё испортится.
			/// Действительно, если мы не выполним обещание о развороте для вершины l сейчас (при условии, что
			/// это обещание есть, то есть pool[l].to_reverse == true), то если мы его не выполним, то мы в итоге
			/// НЕ развернём часть массива, соответствующую вершине pool[l].l (а должны были), но развернём часть
			/// массива, соответствующую r (а не должны были, точнее, сделаем это лишний раз).
			push(l);
			/// push(r) делать не обязательно, так как мы никаким образом не нарушили целостность поддерева r.
			/// Разумеется, можно всё равно вызвать push(r), это ничего не испортит, но это просто не нужно.
			pool[l].r = merge(pool[l].r, r);
			/// Поменяли у вершины левого или правого ребёнка -- делаем recalc!
			recalc(l);
			return l;
		}
		else
		{
			/// А вот здесь мы нарушаем целостность поддерева вершины r и поэтому делаем push для ней.
			push(r);
			pool[r].l = merge(l, pool[r].l);
			/// Поменяли у вершины левого или правого ребёнка -- делаем recalc!
			recalc(r);
			return r;
		}
	}

public:
	/// Построить дерево по подотрезку массива [l, r).
	int build_subtree(const vector<int> &numbers, const int l, const int r)
	{
		/// -1 -- условный номер пустой декартки.
		if (l >= r)
			return -1;
		/// Если мы избавились от приоритетов, то можно строить дерево полностью сбалансированным. Это сложно строго
		/// доказать. Раньше нам мешало то, что приоритеты для полностью сбалансированного дерева существенно
		/// неслучайны, то есть нам могут подсунуть плохую последовательность операций. Но теперь мы выбираем порядок
		/// склейки уже в процессе выполнения самих операций.
		const int m = (l + r) / 2;

		const int left = build_subtree(numbers, l, m);
		const int right = build_subtree(numbers, m + 1, r);
		return add_node(node(left, right, numbers[m]));
	}

	/// Преобразовать настоящий массив в неявное декартово дерево.
	int build_treap(const vector<int> &numbers)
	{
		/// Мы избавились от приоритетов, теперь нам не нужно их порождать.
		return build_subtree(numbers, 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);
	}

	void reverse_segment (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);
		/// Обещаем развернуть среднюю часть.
		promise_reverse(mid);
		/// Склеиваем куски обратно, в том же порядке.
		root = merge(merge(left, mid), right);
	}
};

int main()
{
}