\begin{center}
\textit{Автор задачи и разработчик: Александр Бабин}
\end{center}

\textbf{Подзадача 1.}

В этой подзадаче перестановка восстанавливается следующим образом:

$$
p = [1, f(1,2), 2, f(2,3), 3, \ldots, n-1, f(n-1, n), n]
$$

\textbf{Подзадача 2.}

В этой подзадаче можно было заранее сделать всевозможные запросы $f(i, j)$, а затем восстановить перестановку за время $O(n^2)$. Сделать это можно следующим образом:

\begin{itemize}
\item Пусть $g(x)$~--- это количество таких $y$ ($1 \le y \le n$), что $f(x,y)=1$.
\item Ясно, что любой элемент $x \neq 1$ находится на расстоянии $\frac{n+1}{2}-g(x)$ от единицы.
\end{itemize}

Поставим единицу на позиицию $\frac{n+1}{2}$ в перестановке и произвольным образом расставим элементы, которые должны быть на расстоянии ровно $1$ от нее. Так можно сделать, ввиду того, что функция $f$ не изменяется от применения к перестановке операции циклического сдвига и разворота.

Для каждого элемента $x$ на расстоянии  $\le \frac{n-3}{2}$ от единицы можно однозначно восстановить, в какой половине перестановки он находится, для этого достаточно проверить равенство $f(p_{\frac{n-1}{2}}, x) = 1$. В случае если это равенство выполняется, элемент лежит в правой половине, а иначе~--- в левой.

Расположение же элементов $p_1$ и $p_n$ можно перебрать и проверить наивно корректность всех запросов. В некоторых случаях однозначно восстановить их взаимное расположение невозможно.

\textbf{Подзадача 3.}

Эта подзадача гарантировала, что решения лучше квадратичных смогут набрать хоть какие-то баллы.


\textbf{Решение на 70+ баллов. (Вероятностное, сложное, но доказуемое)}

Решение можно разбить на три фазы:

\textit{Фаза 1. Разбиение элементов на две половины относительно единицы.}

Будем поддерживать 5 множеств элементов $L$~--- множество элементов, которые находятся левее единицы, $R$~--- множество элементов, которые находятся правее единицы, $L' \subset L$, $R' \subset R$ и $C$~--- множество элементов на расстоянии $\frac{n-1}2$ от единицы. Множества $L'$ и $R'$ будут содержать какое-то подмножество самых близких к единице элементов из множеств $L$ и $R$.

Выберем случайный элемент $x$, для которого мы еще не смогли определить, с какой стороны он находится:

\begin{itemize}
\item Если $L = R = \emptyset$, то сформируем множество $R = R' = \{ y \,|\, f(x,y)=1 \}$. В ином случае гарантируется, что $L' \neq \emptyset$ и $R' \neq \emptyset$ (см. следующий пункт) и тогда можно сформировать пару множеств $L(x) = \{ y \in L' \,|\, f(x,y)=1 \}$ и $R(x) = \{ y \in R' \,|\, f(x,y)=1 \}$.
\begin{itemize}
\item Если $L(x) = R(x) = \emptyset$, то элемент $x$ находится на расстоянии $\frac{n-1}2$ от единицы и он является \textit{угловым}, поэтому он добавляется в множество $C$ и следующий пункт алгоритма не производится.
\item Если $R(x) \neq \emptyset$, то $L(x) = \emptyset$. Значит, можно сформировать $R' \gets R(x)$ и отнести $x$ в левую половину.
\item Если $L(x) \neq \emptyset$, то $R(x) = \emptyset$ и надо присвоить $L' \gets L(x)$.
\item Необязательно одновременно формировать множества $L(x)$ и $R(x)$, сначала можно проверить на пустоту одно, и только при необходимости сформировать второе множество.
\end{itemize}

\item Положим, что мы определили, что $x$ лежит в левой половине (т.е. в предыдущем пункте мы изменяли $R'$), тогда возьмем произвольный случайный элемент $y \in R'$ после обновления. И сформируем множество $L(y) = \{ z \not \in L \cup R \,|\, f(z,y)=1 \} \cup \{ x \} \cup L$, присвоив $L \gets L(y)$. Если $L' = \emptyset$, то присвоим $L' \gets L$.

\item Аналогично поступим, если $x$ лежит в правой половине.
\end{itemize}

Таким образом если повторять два пункта выше, то значения $2,\ldots, n$ в коцне концов разобьются на $3$ группы $L, R, C$~--- левые значения, правые значения  и угловые. Заметим, что в ходе выполнения алгоритма множества $L(x)$, $R(x)$, $L(y)$, $R(y)$ при условии своей непустоты совпадали с $\{ z \,|\, f(x,z)=1 \}$ или $(\{ z \,|\, f(y,z)=1 \}$ (доказательство в качестве упражнения). Более того, можно показать, что при каждой операции величина $n-|L(x)|-|R(x)|$ уменьшалась в среднем в два раза, а также примерно в два раза уменьшалась размер $L'$ или $R'$. То есть первая фаза требует $O(n)$ запросов. Разумеется, можно произвести более аккуратный анализ и строго вычислить математическое ожидание количества запросов.

Обозначим $G(x) = \{ y \,|\, f(x,y)=1 \}$. Так как  мы уже определили для некоторых элементов $G(x)$, а также для всех элементов определили с какой стороны от единицы они располагаются, то для таких элементов мы уже однозначно умеем восстанавливать их позицию. Более того, различные значения вычисленных множеств $G(x)$ для $x \in L$ позволяют разбить все элементы из $y$ на группы подряд идущих на цикле значений. Действительно, если $G(x_1) \subset G(x_2)$, $x_1, x_2 \in L$, то все элементы из $G(x_1)$ находятся к единице ближе, чем элементы из $G(x_2) \backslash G(x_1)$.

\textit{Фаза 2. Уточнение позиций элементов из $L$ и $R$.}

Разобьем все элементы из $R$, на блоки $L \backslash G(x_1)$, $G(x_1) \backslash G(x_2)$, $G(x_2) \backslash G(x_3)$, \ldots, $G(x_{k-1}) \backslash G(x_k)$, где $x_i \in L$ и $G(x_k) \subset G(x_{k-1}) \subset \ldots \subset G(x_1) \subset L$, пусть это блоки $B_1, \ldots, B_k$. Для каждого блока  $B_i$ можно определить множество позиций, которые занимают значения из $B_i$ и между разными блоками эти множества позиций не пересекаются. Более того, ясно, что если в каком-то блоке содержится ровно одно значение $x \in B_i$, позиция которого неизвестна, то ее можно сразу восстановить.

Таким образом, чем больше значений $G(x)$ ($x \in L$) мы знаем, тем точнее можно расставить элементы из правой половины. Значения $x \in L$ точно также можно разбить по блокам, руководствуясь вычисленными множествами $G(y)$ ($y \in R$).

Если мы выберем случайный $x \in L$, для которого еще неизвестна его позиция, то необязательно проверять все $y \in R$, чтобы сформировать $G(x)$. Во-первых, есть значения $x' \in L$, для которых мы знаем $G(x')$ и которые гарантированно находятся или левее, или правее $x$ (исходя из деления по блокам левой половины), то из этого мы можем заключить $G(x) \subset G(x')$ или $G(x') \subset G(x)$ в зависимости от взаимного расположения. Во вторых, зная значения $G(y)$ ($y \in R$) также можно сузить отрезок значений, для которых неизвестно, должны ли они лежать в $G(x)$ ($x \in G(y) \Leftrightarrow y \in G(x)$ + что-то известно про взаимное расположение блоков и уже поставленных на место элементов).

После этих отсечений остается только какой-то отрезок блоков из правой половины $B_l, \ldots, B_r$, для элементов которых неизвестно лежат они в $G(x)$ или нет. Сначала будут идти блоки, которые не лежат в $G(x)$, потом, блок, который частично лежит в $G(x)$, а затем блоки, которые полностью содержатся в $G(x)$. Поэтому можно воспользоваться бинарным поиском и за $\log_2 (r - l)$ определить пару блоков, которые возможно, частично лежат в $G(x)$. А затем уже за сумму размеров этих блоков определяем, какой из блоков лежит частично и делим его на пару блоков.

Таким образом мы придумали достаточно экономный по запросам способ делить блоки на еще меньшие блоки. Предлагаемое решение выбирает случайно элемент $x$ для которого неизвестно $G(x)$ (выбираются равновероятно и элементы из $L$ и элементы из $R$), а затем выполняется описанная процедура разделения блоков. В конце концов все блоки делятся на блоки размера $1$ и происходит победа. Разумеется, множества $G(x)$ не поддерживаются напрямую, вычисляется только разбиение на блоки.

Эту часть можно реализовать так, чтобы она работала за $O(n \log n)$ по мат ожиданию времени работы. Для этого достаточно работать за время $O(|B_x|+|B_a|)$~-- где $B_x$~--- размер блока, где находится $x$, а $|B_a|$~--- суммарный размер блоков из другой половины, которые оказались интересными для рассмотрения.

\textit{Фаза 3.}

После третьей фазы восстановились все значения $p_2, \ldots, p_{n-1}$ ($p_{\frac{n+1}2} = 1$), остается только расположить элементы из $C$ (угловые элементы) на позициях $p_1$ и $p_n$. Это не всегда можно сделать однозначно, но утверждается, что достаточно рассмотреть значения $f(c, p_2)$ и $f(c, p_{n-1}$) ($c \in C$) и по ним восстановить любое подходящее расположение угловых элементов.

Не легко, но плюс-минус интуитивно, можно показать, что математическое ожидание количества запросов у такого решения не превышает $O(n \log n)$.

\textbf{Решение на 85+ баллов. (Теория информации) }

Пусть мы находимся на второй фазе алгоритма. По сути, уже определены $C$~--- угловые элементы (на расстоянии $\frac{n-1}2$ от единицы), определены позиции некоторых элементов, а остальные элементы разбиты на блоки $B_1, \ldots, B_k$, где каждый блок состоит из каких-то значений, для которых известно, что они находятся на каком-то множестве подряд идущих значений, на которых еще не стоят восстановленные элементы перестановки (какой-то найденный элемент при этом может стоять между какими-то двумя возможными позициями для одного блока), при этом эти множества позиций не пересекаются.

Тогда, имея эту информацию возможно $2^J = |B_1|! \cdot |B_2|! \cdot \ldots \cdot |B_k|!$ возможных перестановок, количество информации $J$ вычисляется, соответственно, как $J = \sum_{i=1}^k \log_2 |B_i|! = \sum_{i=1}^k \sum_{j=1}^{|B_i|} \log_2 j$. Во многих задачах применима эвристика на основе теории информации~--- достаточно выбирать жадную стратегию, которая на каждом шаге максимизирует отношение уменьшения количества информации к количеству потраченных запросов, т.е. максимизируется математическое ожидание величины $\frac{-\Delta J}{\Delta q}$ по всем допустимым шагам, где $\Delta J$~--- это количество информации после очередного шага, а $\Delta q$~--- потраченное на этот шаг количество запросов.

В нашем случае, шаг заключается в том, что мы выбираем какой-то элемент $x$ с неизвестной позицией, а затем находит для него $G(x)$ ($G(x) = \{ y \,|\, f(x,y)=1 \}$), после чего узнаем позицию элемента $x$, а также разрезаем какой-то блок на две части.

Рассчитаем количество запросов и уменьшение количества информации, которое произойдет, если мы определим позицию элемента с номером $i$:

\begin{itemize}
\item $- \Delta J = \log_2 |B(i)| - \log_2 (X!) - \log_2 (Y!) + \log_2 ((X+Y)!)$, где $|B(i)|$~--- размер блока, в котором содержится элемент $i$, а $X$ и $Y$~--- это размеры блоков, на которые разрезается блок, после нахождения блока $i$.
\item $\Delta q \approx X+Y + \log_2 M(i)$, где $X$ и $Y$~--- те же величины, что и в прошлом пункте, а $M(i)$~--- количество блоков, которые может разрезать элемент $x'$, находящийся в том же блоке, что и $x$.
\end{itemize}

Соответственно, математическое ожидание отношения полученной информации к затраченным действиям $E[- \frac{\Delta J}{\Delta q}]$ для конкретного блока $B_j$ равно средне арифметическому $\frac{-\Delta J}{\Delta q}$ для всех возможных индексов $i \in B_j$, где могут лежать элементы из $B_j$. И жадная стратегия будет заключаться в том, чтобы взять случайное значение из того блока, в котором это матожидание как можно больше.

Остается только научиться пересчитывать все описанные значения. Удивительно, но это все можно делать наивно, суммарное количество изменений $\Delta J$ и $\Delta q$ по всем индексам оказывается не очень большим.

\textbf{Решение на 100+ баллов. (Дерево минимумов)}

Предположим, что мы разделили все элементы на $3$ группы $L, R, C$ (читать первую фазу алгоритма на 70 баллов). Тогда можно потратить $n \log_2 n$ запросов на построение дерево миниумов по элементам $L$ и по элементам $R$. Деревом минимумов называется дерево, которое строится для массива $[a_1, \ldots, a_n]$ следующим образом:

\begin{itemize}
\item Выбирается минимальный по значению элемент $a_i$, он становится корнем дерева, а левым и правым сыновьями этой вершины становятся деревья минимумов, построенные для подотрезков $a[1 \ldots, i-1]$ и $a[i+1, \ldots, n]$.
\end{itemize}

Легко заметить, что если мы выбираем два значения $x, y \in L$, то $f(x, y)$ будет равняться LCA вершин $x$ и $y$ в дереве миниумов для подотрезка перестановки, где располагаются элементы из $L$. 

Для построения дерева минимумов для множества $L$ можно постепенно добавлять в него элементы в порядке возрастания. Пусть мы добавляем элемент $x$, тогда можно выделить путь из корня в уже построенном дереве, который всегда идет в большее поддерево. Если этот путь заканчивается в листе $y$, то после запроса $f(x,y)$ мы понимаем, LCA вершин $x$ и $y$, то есть тот момент, в который надо сойти с этого пути. Сошли с пути~--- зашли в поддерево в два раза меньше, можем повторить запрос, за $O(\log n)$ запросов смогли понять, куда подвесится вершина $x$. Единственным нюансом является тот факт, что в построенном дереве непонятно, какие сыновья левые, а какие правые, но даже без этой информации построенное дерево помогает ускорить вторую фазу алгоритма.

Заметим, что когда разрежется какой-то блок или из блока мы узнаем значение какого-то элемента и его понадобится вырезать из дерева минимумов, то мы все спокойно сможем пересчитать и не будет никак проблем. Достаточно разрезать исходное дерево минимумов на минимальное количество деревьев, а потом корни полученных деревьев соединить в одно дерево тем же алгоритмом.

Тепрь рассмотрим то, почему дерево минимумов в принципе может помогать. Пусть у нас есть элемент $x$ и набор блоков с построенными деревьями $B_1, \ldots, B_n$, а в данный момент мы разрезаем элементом $x$ какой-то блок $B$. Обозначим $a(v) = 1$ ($v \in B$), если $f(x,v)=1$ и $a(v) = 0$ в ином случае. Есть следующие отсечения:

\begin{itemize}
\item Если $v$~--- корень, а $l$ и $r$~--- какие-то вершины из его разных поддеревьев, то если $a(v) \neq a(l)$, то $a(v) = a(r)$.  
\item Если $v$~--- корень, а в одном из его поддеревьев есть $y$ ($a(y) \neq a(v)$), то можно отделить от дерева $v$ сына, в поддереве которого лежит вершина $y$, и однозначно восстановить какое дерево левее, а какое правее (то есть дополнительно разделить все на блоки).
\item Вычислять значения $a(v) = f(x,v)$ выгодно в порядке убывания размеров поддеревьев $v$.
\end{itemize}

Эта пара отсечений работает хорошо, так как разрезает блок, не на один блок, а по крайней мере на $\Omega(\log (n))$ по матожиданию, если разрезать блоки в случайных местах. Более того, такой способ дает некоторые гарантии (сейчас будет рукомахание, но все же):

\begin{itemize}
\item Мы режем дерево в случайном месте, поэтому чаще всего $f(v,x)=1$ и $f(v,x) \neq 1$ будет встречаться примерно с соизмеримой вероятностью. Поэтому будет очень часто работать отсечение по первому пункту и мы сделаем мало запросов на сбалансированном дереве.
\item Если же мы режем дерево не в равной пропорции, то мы сделаем много запросов, но и разрежется много ребер, потому что мы достаточно глубоко спустимся.
\end{itemize}