Для подготовки к олимпиаде <<Когнитивные Технологии>> Мадока решила все задачи в мире на сортировки перестановок. Но жюри смогли удивить ее, и дали задачу, которую она нигде до этого не видела, и она не смогла решить ее. Вот она:

Дана перестановка $p_1, p_2, \ldots, p_n$. С ней можно выполнять следующую операцию:
\begin{itemize}
\item выбрать пару различных индексов $i, j$ ($1 \le i, j \le n$), где $p_i = 1$ и $|i - j| \le \frac{n}{2}$
\item поменять местами $p_i$ и $p_j$.
\end{itemize}

Нужно отсортировать перестановку не более, чем за $4 \cdot n$ операций, либо сообщить, что это невозможно.