Перестановка длины $$$n$$$ — это последовательность целых чисел от $$$1$$$ до $$$n$$$ такая, что каждое число встречается в ней ровно один раз.

Назовем неподвижностью перестановки $$$p$$$ количество неподвижных точек в ней — количество позиций $$$j$$$ таких, что $$$p_j = j$$$, где $$$p_j$$$ — $$$j$$$-й элемент перестановки $$$p$$$.

От вас требуется построить последовательность перестановок $$$a_1, a_2, \dots$$$, начав с тождественной перестановки (перестановки $$$a_1 = [1, 2, \dots, n]$$$). Назовем это цепочкой перестановок. Таким образом, каждое $$$a_i$$$ — $$$i$$$-я перестановка длины $$$n$$$.

Для каждого $$$i$$$ от $$$2$$$ и дальше перестановка $$$a_i$$$ должна быть получена из перестановки $$$a_{i-1}$$$ обменом двух элементов местами (не обязательно соседних). Неподвижность перестановки $$$a_i$$$ должна быть строго меньше неподвижности перестановки $$$a_{i-1}$$$.

Рассмотрим некоторые цепочки для $$$n = 3$$$:

• $$$a_1 = [1, 2, 3]$$$, $$$a_2 = [1, 3, 2]$$$ — это валидная цепочка длины $$$2$$$. От $$$a_1$$$ к $$$a_2$$$ элементы на позициях $$$2$$$ и $$$3$$$ меняются местами, неподвижность уменьшается с $$$3$$$ до $$$1$$$.
• $$$a_1 = [2, 1, 3]$$$, $$$a_2 = [3, 1, 2]$$$ — это не валидная цепочка. Первая перестановка всегда должна быть $$$[1, 2, 3]$$$ для $$$n = 3$$$.
• $$$a_1 = [1, 2, 3]$$$, $$$a_2 = [1, 3, 2]$$$, $$$a_3 = [1, 2, 3]$$$ — это не валидная цепочка. От $$$a_2$$$ к $$$a_3$$$ элементы на позициях $$$2$$$ и $$$3$$$ меняются местами, но неподвижность увеличивается с $$$1$$$ до $$$3$$$.
• $$$a_1 = [1, 2, 3]$$$, $$$a_2 = [3, 2, 1]$$$, $$$a_3 = [3, 1, 2]$$$ — это валидная цепочка длины $$$3$$$. От $$$a_1$$$ к $$$a_2$$$ элементы на позициях $$$1$$$ и $$$3$$$ меняются местами, неподвижность уменьшается с $$$3$$$ до $$$1$$$. От $$$a_2$$$ к $$$a_3$$$ элементы на позициях $$$2$$$ и $$$3$$$ меняются местами, неподвижность уменьшается с $$$1$$$ до $$$0$$$.

Найдите самую длинную цепочку перестановок. Если есть несколько самых длинных ответов, то выведите любой из них.