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

Для фиксированного целого положительного числа $$$d$$$ назовем ценой перестановки $$$p$$$ длины $$$n$$$ количество таких индексов $$$i$$$ $$$(1 \le i < n)$$$, что $$$p_i \cdot d = p_{i + 1}$$$.

Например, если $$$d = 3$$$, а $$$p = [5, 2, 6, 7, 1, 3, 4]$$$, то цена такой перестановки равна $$$2$$$, т.к. $$$p_2 \cdot 3 = p_3$$$ и $$$p_5 \cdot 3 = p_6$$$.

Ваша задача — для заданного $$$n$$$ найти перестановку длины $$$n$$$ и значение $$$d$$$, что цена перестановки максимально возможная (среди всех способов выбрать перестановку и значение $$$d$$$). Если оптимальных ответов несколько — выведите любой.