$$$a^2 \equiv 0, 1 $$$ $$$(mod$$$ $$$4)$$$. Давайте попробуем использовать это в решении.

Мы хотим, чтобы префиксы были сравнимы с $$$2$$$ и $$$3$$$ по модулю $$$4$$$. То есть прибавляя очередной элемент перестановки, остаток должен оставаться $$$2$$$ или $$$3$$$. Тогда заметим, что $$$2+1 \equiv 3$$$, $$$3+3 \equiv 2$$$, $$$2+4 \equiv 2$$$, $$$3+4 \equiv 3$$$ $$$(mod$$$ $$$4)$$$. То есть если у нас изначально остаток $$$2$$$, то мы можем прибавлять числа в таком порядке: $$$+$$$ число сравнимое с $$$1$$$, $$$+$$$ число сравнимое с $$$3$$$, $$$+$$$ число сравнимое с $$$4$$$ и так по кругу. Тогда все префиксы будут сравнимы по модулю $$$4$$$ с $$$2$$$ или $$$3$$$ и все хорошо.

Нам остается решить проблему с остатком $$$2$$$. Действительно, прибавляя его к $$$2$$$, мы получаем $$$0$$$, а прибавляя его к $$$3$$$, мы получаем $$$1$$$.

Раз этот остаток $$$2$$$ нам так не удобен, давайте попробуем его запихнуть в самое начало. То есть ответ будет начинаться, как $$$2, 6, 10...$$$.

И вот совпадение: сумма таких чисел не может являться квадратом. Дело вот в чем: $$$2+6+..+(4k+2) = 2\cdot(1+3+..+(2k+1))$$$. Сумма первых нескольких нечетных чисел как известно квадрат натурального числа, а значит наше число это удвоенный квадрат натурального числа, что не может являться квадратом.

Остается решить последнюю проблему. Такая сумма может быть сравнима с $$$0$$$ по модулю $$$4$$$. Например если $$$n = 9$$$, то на начале у нас будут числа $$$2$$$ и $$$6$$$, а $$$2+6$$$ сравнимо с $$$0$$$ по модулю $$$4$$$. Тогда давайте просто перенесем наибольшее число, сравнимое с $$$2$$$ по модулю $$$4$$$ в конец. Действительно, ничего не могло испортиться, ведь это число будет участвовать только в префиксе, совпадающим со всем массивом, а сумма всех чисел массива — не квадрат.

$$$n = 9:$$$

$$$[2, 1, 3, 4, 5, 7, 8, 9, 6]$$$

• $$$2$$$ — префикс из остатков $$$2$$$
• $$$2+1 \equiv 3$$$ — не квадрат (Далее сумму на префиксе до $$$i$$$ заменяем на остаток по модулю $$$4$$$)
• $$$3+3 \equiv 2$$$ — не квадрат
• $$$2+4 \equiv 2$$$ — не квадрат
• $$$2+5 \equiv 3$$$ — не квадрат
• $$$3+7 \equiv 2$$$ — не квадрат
• $$$2+8 \equiv 2$$$ — не квадрат
• $$$2+9 \equiv 3$$$ — не квадрат
• В конце находится $$$6$$$, которую мы перенесли в конец из префикса остатков $$$2$$$.

$$$n = 12:$$$

$$$[2, 6, 10, 1, 3, 4, 5, 7, 8, 9, 11, 12]$$$

• $$$2, 6, 10$$$ — префикс из остатков $$$2$$$
• $$$2+1 \equiv 3$$$ — не квадрат
• $$$3+3 \equiv 2$$$ — не квадрат
• $$$2+4 \equiv 2$$$ — не квадрат
• $$$2+5 \equiv 3$$$ — не квадрат
• $$$3+7 \equiv 2$$$ — не квадрат
• $$$2+8 \equiv 2$$$ — не квадрат
• $$$2+9 \equiv 3$$$ — не квадрат
• $$$3+11 \equiv 2$$$ — не квадрат
• $$$2+12 \equiv 2$$$ — не квадрат