Назовем преобразованием последовательности из \(n\) элементов следующий процесс:
Если последовательность пуста, то процесс завершается. Иначе допишем к ответу наибольший общий делитель (НОД) всех элементов последовательности, удалим один любой элемент последовательности и продолжим процесс. В результате на бумаге получится последовательность из \(n\) чисел — наибольшие общие делители всех чисел последовательности перед каждым удалением.
Изначально дана последовательность целых чисел \(1, 2, \dots, n\). Найдите лексикографически максимальный результат преобразования этой последовательности.
Последовательность \(a_1, a_2, \ldots, a_n\) лексикографически больше последовательности \(b_1, b_2, \ldots, b_n\), если существует такой индекс \(i\), что \(a_j = b_j\) для всех \(j < i\), и при этом \(a_i > b_i\).
Примечание
В первом примере результат достигается так:
- Запишем НОД\((1, 2, 3) = 1\) и удалим \(2\).
- Запишем НОД\((1, 3) = 1\) и удалим \(1\).
- Запишем НОД\((3) = 3\) и удалим \(3\).
В результате преобразования будет написана последовательность \([1, 1, 3]\).