Напомним, что перестановка длины \(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\)). Если оптимальных ответов несколько — выведите любой.