Во-первых, давайте разберемся со случаем $$$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$$$ свапов.