Во-первых, давайте разберемся со случаем $n = 3$. Заметим, что в нем мы можем менять местами только $1$ и его соседа. А значит относительный порядок $2$ и $3$ не поменяется. Поэтому проверяем что их порядок нужный, то ответа нет. Иначе ответ есть и следующий алгоритм явно его строит:

Основная идея: пусть мы поставили $i - 1$ самых больших элементов в самый конец в нужном порядке. Тогда мы хотим научиться ставить элемент $n - i$ на позицию $n.- i$. Если $n - i <= \frac{n}{2}$, то значит, что $1$ можно менять с любыми элементами, а значит можно поставить за одно действие $1$ на место $n - i$, а следующим единицу поменять с нужным элементом.

Теперь научимся ставить элемент в оставшимся случае. Идея: давайте поставим $1$ на позицию $\frac{n}{2}$, затем при помощи этого поставим $n - i$ на эту позицию. Так как единицу на позиции $\frac{n}{2}$ можно менять местами с любыми элементами. Потом ставим единицу на позицию $\frac{n}{2} + 1$. Благодаря этому мы сможем поставить единицу на позицию $n - i$. А оттуда ее можно поменять местами с $\frac{n}{2}$, тем самым поставив элемент $n - i$ в нужную позицию. Правда в этом случае нужно рассмотреть аккуртно случаи, когда мы никак не меняем позицию элемента в этом случае. И их игнорировать.

В итоге для второго случая нам нужно не более $5$ операций на то, чтобы одно число поставить на нужную позицию, а для первого не более одного. В итоге получаем, что этот алгоритм работает меньше, чем за $3n$ свапов.